Problem description

Given a sequence of length $n$, you can add a positive or negative sign to any number to find the number of consecutive sub-segments with a sum of 0.

Input format

The first line contains $n$ ($1\le n\le1000$). The second line contains $a_1,a_2...a_n$ ($1\le a_i\le 1000$), and the sum of the sequence is less than or equal to 10000.

Output format

Output the number of solutions modulo $10^9+7$ where the sum of consecutive sub-segments is 0.

4 
1 1 1 1 

12