First Grade

Sanggeun loves addition and subtraction. Whenever he sees a row of digits, he places an = between the last two numbers and a + or - between every other pair of adjacent numbers, forming a single equation. For example, from the sequence 8 3 2 4 8 7 2 4 0 8 8 he can build the equation 8+3-2-4+8-7-2-4-0+8=8.

Sanggeun only wants to build valid equations. He has not learned about negative numbers yet, and he does not know any number greater than 20. Therefore, when the left-hand side is evaluated strictly from left to right, every intermediate value must always be between $0$ and $20$, inclusive. For example, 8+3+2-4-8-7+2+4+0+8=8 is a correct equation on its own, but evaluating it from the left makes 8+3+2-4-8-7 negative, so Sanggeun cannot build it.

Given a sequence of digits, write a program that counts how many valid equations Sanggeun can build.

The first line contains the number of digits $N$ ($3 \le N \le 100$). The second line contains $N$ integers between $0$ and $9$, inclusive, separated by spaces.

Print, on the first line, the number of valid equations Sanggeun can build. This value is at most $2^{63}-1$.

For the sequence 8 3 2 4 8 7 2 4 0 8 8, the following 10 equations can be formed:

• 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