Problem Description

JOI is a first grader. He is very fond of addition and subtraction which he has just learned. Whenever he sees a sequence of numbers, he likes to put = between the last two numbers and always put + or - between the remaining numbers to form an equation. For example, from 8 3 2 4 8 7 2 4 0 8 8, he can form the equation 8+3-2-4+8-7-2-4-0+8=8.

After forming an equation, JOI checks if it is a correct equation by calculating it. However, he does not know about negative numbers yet and cannot perform calculations that exceed 20. Therefore, among the correct equations, only those where all intermediate numbers in the calculation from left to right are between 0 and 20 inclusive can be verified by JOI. For example, 8+3-2-4-8-7+2+4+0+8=8 is a correct equation, but since 8+3-2-4-8 results in a negative number, JOI cannot verify if this equation is correct.

Given a sequence of numbers, write a program to find the number of correct equations that JOI can form and verify.

Input Format

The input consists of 2 lines. The first line contains an integer $ N $ ($3 \leq N \leq 100$), which represents the number of numbers in the sequence. The second line contains $ N $ integers between 0 and 9, separated by spaces.

In 60% of the input data, the number of correct equations that JOI can form and verify does not exceed $ 2^{31}-1 $. In all input data, the number of correct equations does not exceed $ 2^{63}-1 $.

Output Format

Output a single line containing an integer representing the number of correct equations that JOI can form and verify.

Sample Input and Output

Sample Input #1

11
8 3 2 4 8 7 2 4 0 8 8

Sample Output #1

10

Sample Input #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

Sample Output #2

7069052760

Notes/Hints

Sample Explanation 1

In the first sample input, JOI can form and verify 10 correct equations, such as 8+3-2-4+8-7-2-4-0+8=8. Therefore, the output is 10.

Sample Explanation 2

In the second sample input, note that the answer does not fit within the range of a 32-bit signed integer.

见题面 Input 部分

见题面 Output 部分