E. 令人费解的密码*

描述 情报人员收到一组密码（N个以空格分隔的单个数字），但是这组密码可能存在问题。经过分析，情报人员发现原因是在解码过程中，数字2可能被错误地解释成了两个1。例如，1 1 1 3 1 2 的原始内容可能是2 1 3 1 2，或者1 2 3 1 2，当然也可能就是1 1 1 3 1 2。

请编写一个程序，对于每次收到的密码，求原始内容可能有多少种情况？

友情提示：

由于答案可能很大，为便于评测，请同学们使用 unsigned long long 定义变量或数组。

输入 第一行1个整数N；

第二行N个以空格分隔的数字，表示这组密码。

输出 输出一个整数，表示原始内容可能的情况数量。

输入

6

1 1 1 3 1 2

输出

3

输入

19

3 5 1 1 1 2 6 1 1 1 1 2 1 1 2 2 3 7 0

输出

30