A. Rajaee in the Kitchen
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Today is Rajaee's birthday!! $$$Who$$$ $$$Asked?$$$

Sadly, no one remembered his birthday, so he decided to make a birthday cake by himself. He went searching in the kitchen for suitable ingredients, but unfortunately, he found nothing but an array of positive integer numbers. He is going to make a cake out of this array using the following technique:

  • Firstly, he divides the array into several consecutive non-empty subarrays.
  • Every element of the array should belong to exactly one subarray.
  • Then for each subarray, he creates an edge of length equal to the sum of the numbers in the subarray.
  • Then he forms a cake in the shape of a convex polygon using all the edges he created.

Rajaee is wondering in how many ways he can divide the array into smaller subarrays such that he can make a cake out of it. Rajaee is too bad at maths so he needs your help to know the number of ways modulo $$$10^9 + 7$$$.

Two ways are considered different if there exists an element with index $$$i$$$ belonging to two different subarrays in each way.

Input

The first line contains a single integer number $$$N$$$ $$$(3 \le N \le 10^6)$$$, the size of the array.

The second line contains $$$N$$$ integer numbers $$$a_1, a_2,.., a_N$$$ $$$(1 \le a_i \le 10^9)$$$, the elements of the array.

Output

Output the number of ways modulo $$$10^9 + 7$$$.

Examples
Input
3
3 4 5
Output
1
Input
6
1 5 2 4 1 2
Output
18
Input
10
7 2 3 5 8 3 1 9 4 5
Output
436