First Grade

Interview

Time limit1sMemory limit128 MB

Summary

Count the ways to place + or - between the first N-1 digits and = before the last digit so that left-to-right evaluation never leaves the range 0 to 20 and the total equals the last digit.

Level: Medium6 of 10
Topics: Dynamic programming, Array
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Hint

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

Examples2

Example 1
Input
```
11
8 3 2 4 8 7 2 4 0 8 8
```
Expected output
```
10
```

Example 2

Input

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

Expected output

7069052760