You are given an array of integers [a_1, a_2, \ldots, a_n]. In one operation you can do the following:
Choose some with 2\le i \le n-1.
Let a_i = x. Then add to a_{i-1} and a_{i+1}, and replace a_i by .
For example, if the array was [1, 2, -1, 3], we can choose i = 3, perform the operation, and obtain the array [1, 1, 1, 2].
You can apply this operation to the array any number of times. How many different arrays can you obtain? If you can obtain infinitely many arrays, print ; otherwise print the number of these arrays modulo 10^9 + 7.
Two arrays are considered different if they differ in at least one position.
The first line contains one integer (3 \le n \le 10^5) — the length of the array.
The second line contains integers a_1, a_2, \ldots, a_n (-10^9 \le a_i \le 10^9) — the elements of the array.
If you can obtain infinitely many arrays, print ; otherwise print the number of these arrays modulo 10^9 + 7.
Example 1
Example 2
Example 3
In the first sample, we can apply the operation only for i = 2, which gives two different arrays: [18, 9, 2021] and [27, -9, 2030].
In the second sample, whichever operation we apply, the array stays equal to [0, 0, 0, 0, 0].