Unifying Values

Interview

Time limit0.5sMemory limit1024 MB

Summary

Count the ways to split a sequence of N integers into two or more contiguous parts with equal sums, modulo 1,000,000,007.

Level: Medium6 of 10
Topics: Prefix sum, Hash map, Dynamic programming, Math
Solved: No attempts yet

Problem

A sequence of $N$ integers is given. You may split the sequence into two or more contiguous parts and compute the sum of the numbers in each part. Count the number of ways to split the sequence so that every part has the same sum.

For example, let the sequence be $[4, -3, 1, 0, 1]$ . You can split it into three parts $[4, -3]$ , $[1]$ , $[0, 1]$ , or into three parts $[4, -3]$ , $[1, 0]$ , $[1]$ . In both cases every part sums to $1$ . There are no other ways, so the answer for this input is $2$ .

Input

The first line contains an integer $N$ ( $1 \le N \le 10^4$ ).

The second line contains the $N$ integers of the sequence in order, separated by single spaces. Each integer is between $-10^{14}$ and $10^{14}$ , inclusive.

Output

Print the number of ways to split the sequence. Since this number can be very large, print the remainder when divided by $1\,000\,000\,007$ .

Examples3

Example 1
Input
```
5
4 -3 1 0 1
```
Expected output
```
2
```
Example 2
Input
```
6
1 1 1 1 1 1
```
Expected output
```
3
```
Example 3
Input
```
4
100 200 300 400
```
Expected output
```
0
```