Hongjun and Antimatter

Interview

Time limit2sMemory limit512 MB

Summary

Count contiguous subarrays of length at least 2 that can be split into two disjoint nonempty parts with equal sums, modulo 1e9+7.

Level: Medium7 of 10
Topics: Dynamic programming, Prefix sum, Combinatorics, Array
Solved: No attempts yet

Problem

Hongjun has N pieces of matter laid out in a row. The amount of each piece is a positive integer.

Hongjun picks one contiguous run of pieces, then turns some of the picked pieces into antimatter and casts a spell. The spell succeeds when the total amount still left as matter equals the total amount turned into antimatter. Hongjun cannot cast a spell without picking anything, so he must pick at least 2 contiguous pieces.

Two cases count as different when the chosen run differs, or when the set of pieces turned into antimatter differs. Given the amounts, count the cases in which the spell succeeds.

Input

The first line contains the number of pieces N ( $1 \le N \le 1000$ ).

The second line contains the amount of the i-th piece $a_i$ ( $1 \le a_i \le 10000$ ), separated by spaces.

The sum of all amounts does not exceed 10000.

Output

Print the number of cases in which the spell succeeds, modulo $10^9+7$ .

Examples6

Example 1
Input
```
4
1 1 1 1
```
Expected output
```
12
```
Example 2
Input
```
1
5
```
Expected output
```
0
```
Example 3
Input
```
2
3 3
```
Expected output
```
2
```
Example 4
Input
```
2
1 2
```
Expected output
```
0
```
Example 5
Input
```
3
1 4 5
```
Expected output
```
2
```
Example 6
Input
```
5
1 2 3 4 5
```
Expected output
```
6
```