← 返回题目列表

AtCoder · joi2011yo_d

D. 一年级学生

中文机器翻译题面 查看原题

配点: 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 不在指定位的有符号整数范围内。