鲍勃喜欢一切甜蜜的东西。他最喜欢的巧克力棒由块组成,每块可能含有一个坚果。鲍勃想要将巧克力棒分成多块,以便每个部分恰好包含一个坚果,并且任何断裂线都位于两个相邻块之间。
你被要求计算他可以做到这一点的方法数量。如果两种巧克力破碎方法中的一种在相邻的两块巧克力之间有裂缝,而另一种则没有,则两种破碎巧克力的方法被认为是不同的。
请注意,如果 Bob 没有进行任何断裂,则所有杆将形成一件,并且仍然必须有一个螺母。
输入
输入的第一行包含整数 n (1 ≤ n ≤ 100) — 巧克力块的数量。
第二行包含n个整数ai (0 ≤ ai ≤ 1),其中0代表不带螺母的部件,1代表带螺母的部件。
输出
打印将巧克力分成多个部分以使每个部分恰好包含一个坚果的方法数。
示例
输入 #1
3 0 1 0
输出 #1
1
输入 #2
5 1 0 1 0 1
输出 #2
4
注意
在第一个示例中只有一个螺母,因此路数等于 1 - Bob 不应该进行任何中断。
在第二个示例中,您可以通过四种方式打破障碍:
10|10|1
1|010|1
10|1|01
1|01|01