配点: 100 点
問題
JOI君是小学 1 年级的学生。JOI君非常喜欢刚学会的加法和减法,一看到数字排列在一起,最后的 2 个数字之间就会 = 放入 + ,而其余数字之间一定会放入 - 来组成等式进行游戏。例如 8 3 2 4 8 7 2 4 0 8 8 ,可以构造出等式 8+3-2-4+8-7-2-4-0+8=8 。
JOI君在构造等式后,会计算以确认它是否是正确的等式。但JOI君还不知道负数,也无法计算超过20 的数。因此,在正确等式中,只有当从左到右计算左边时,计算途中出现的数全都不超过 0 以上 20 的等式,JOI君才能确认它是正确的等式。例如,8+3-2-4-8-7+2+4+0+8=8 是正确的等式,但在计算途中出现的 8+3-2-4-8 因为是负数,所以JOI君无法确认这个等式是否正确.
当输入给出数字列时,编写一个程序来求出JOI君能制作并确认正确的表达式等的数量.
入力
输入是 它仅由 2 行.1 行表示排列的数字个数的整数 N (3 \leqq N \leqq 100) 被写下了.2 行是 0 以上 9 以下的整数 N 个,用空格分隔写下.
给出的输入数据的 60 %中,JOI君制作并确认正确等式的数量不会超过 2^{31}-1 。此外,在所有给出的输入数据中,JOI君制作并确认正确的表达式等的数量不会超过 2^{63}-1 。
出力
表示JOI君制作并确认正确等式数量的整数, 1 行输出.
入力例 1
11 8 3 2 4 8 7 2 4 0 8 8
出力例 1
10
入力例 1 中,JOI君可以 10 个正确的等式
- 8+3-2-4+8-7-2-4-0+8=8
- 8+3-2-4+8-7-2-4+0+8=8
- 8+3+2+4-8-7+2-4-0+8=8
- 8+3+2+4-8-7+2-4+0+8=8
- 8+3+2-4+8-7+2+4-0-8=8
- 8+3+2-4+8-7+2+4+0-8=8
- 8-3+2+4-8+7+2+4-0-8=8
- 8-3+2+4-8+7+2+4+0-8=8
- 8-3+2-4+8+7+2-4-0-8=8
- 8-3+2-4+8+7+2-4+0-8=8
并且能够确认,所以 10 输出。
入力例 2
40 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1
出力例 2
7069052760
入力例 2 中,请注意答案 32 不在指定位的有符号整数范围内。