摆放汉堡

题目描述:

Cwt买了N个汉堡（高度分别为1..n），他准备摆出一个好看的序列，然后一口气吃掉。

对于好看的序列，cwt有一个标准：第i个汉堡比第i-1个汉堡高（或低）。

现在你需要告诉cwt汉堡可以摆出多少种好看序列的方法。

输入格式:

第一行一个数N。

下面一行N-1个数， 第i个数如果是1， 表示第i+1个汉堡比第i个汉堡高， 如果是0就表示第i+1个汉堡比第i个汉堡矮。

 

输出格式:

一行一个整数， 表示摆放汉堡好看序列的方法数。

样例输入:

3
1 0

样例输出:

2

提示:

20%: N不超过10

70%: N不超过50

100%：N不超过300

时间限制: 1000ms
空间限制: 256MB

---