问题

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 \le N \le 100$)。第二行包含 $N$ 个不超过 $9$ 的整数，以空格分隔。

在$60\%$的输入数据中，JOI君可以创建和验证的正确等式的数量不超过 $2^{31}-1$。对于所有输入数据，JOI君可以创建和验证的正确等式的数量不超过 $2^{63}-1$。

输出

输出一个整数，表示JOI君可以创建并验证的正确等式的数量。

示例 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 1 1 0 0 1 1

输出示例 2

7069052760

请注意，在示例输入2中，结果已经超出了32位有符号整数的范围。