AT_joi2011yo_d.1 年生 (A First Grader)

JOI 君是一名小学一年级学生。JOI 君非常喜欢刚学会的加法和减法，每当看到一串数字时，他会在最后两个数字之间插入一个等号“=”，并在其余的数字之间必须插入“+”或“-”，从而组成一个等式来玩。例如，从 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 君能够组成并判断为正确的等式的个数。

输入包含两行。第一行是一个整数 $N$（$3 \leq N \leq 100$），表示数字的个数。第二行包含 $N$ 个用空格分隔的整数，每个整数在 $0$ 到 $9$ 之间。

在给定的 $60\%$ 的测试数据中，JOI 君能够组成并判断为正确的等式的个数不会超过 $2^{31}-1$。在所有给定的输入数据中，JOI 君能够组成并判断为正确的等式的个数不会超过 $2^{63}-1$。

输出一个整数，表示 JOI 君能够组成并判断为正确的等式的个数。

样例解释 1

在输入样例 $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

在输入样例 $2$ 中，注意答案可能超出 $32$ 位有符号整数的范围。

由 ChatGPT 4.1 翻译