Problem
JOI-kun is a $1$-st grader in elementary school. JOI-kun loves addition and subtraction, which he has just learned, and whenever he sees a sequence of digits lined up, he plays by inserting = between the last $2$ digits and always inserting + or - between the remaining adjacent digits to make an equation. For example, from 8 3 2 4 8 7 2 4 0 8 8, he can make the equation 8+3-2-4+8-7-2-4-0+8=8.
After making an equation, JOI-kun calculates it to check whether it is a valid equation. However, JOI-kun does not yet know negative numbers, and he cannot calculate numbers exceeding $20$. Therefore, among the valid equations, only those in which all numbers appearing during the calculation when evaluating the left-hand side from left to right are at least $0$ and at most $20$ are valid equations that JOI-kun can verify. For example, 8+3-2-4-8-7+2+4+0+8=8 is a valid equation, but since 8+3-2-4-8, which appears in the middle of the calculation, is a negative number, JOI-kun cannot verify whether this equation is valid.
Given a sequence of digits as input, write a program to find the number of valid equations that JOI-kun can make and verify.
Input
The input file consists of $2$ lines. The $1$-st line contains an integer $N$ ($3 \le N \le 100$) representing the number of lined-up digits. The $2$-nd line contains $N$ integers at least $0$ and at most $9$, separated by spaces.
In $60\%$ of the given input data, the number of valid equations that JOI-kun can make and verify does not exceed $2^{31}-1$. Also, in all of the given input data, the number of valid equations that JOI-kun can make and verify does not exceed $2^{63}-1$.
Output
Output on $1$ line an integer representing the number of valid equations that JOI-kun can make and verify.
Input/Output Examples
Input Example 1
11 8 3 2 4 8 7 2 4 0 8 8
Output Example 1
10
Input Example 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
Output Example 2
7069052760
In Input Example $1$, JOI-kun can make and verify the following $10$ valid equations:
8+3-2-4+8-7-2-4-0+8=88+3-2-4+8-7-2-4+0+8=88+3+2+4-8-7+2-4-0+8=88+3+2+4-8-7+2-4+0+8=88+3+2-4+8-7+2+4-0-8=88+3+2-4+8-7+2+4+0-8=88-3+2+4-8+7+2+4-0-8=88-3+2+4-8+7+2+4+0-8=88-3+2-4+8+7+2-4-0-8=88-3+2-4+8+7+2-4+0-8=8
Therefore, output $10$.
In Input Example $2$, note that the answer does not fit within the range of a $32$-bit signed integer.
(Added on $2015$-$2$-$21$) As pointed out by a user, it was found that there was an error among the equations in the explanation of Input Example $1$. It has now been corrected. The $5$-th equation was 8+3-2-4+8-7+2+4-0-8=8, which has been corrected to 8+3+2-4+8-7+2+4-0-8=8. Also, the $6$-th equation was 8+3-2-4+8-7+2+4+0-8=8, which has been corrected to 8+3+2-4+8-7+2+4+0-8=8.