Problem-writers love coming up with incredibly specific, completely useless properties of an arrays of numbers that they want you to compute for them. Now, we can't have an ICPC tryout contest without one of those problems so here is an especially contrived example to compute:
For a given array $A$, define $psi (A)$ as the number of ways to negate certain elements of $A$ such that the sum of the elements of $A$ is now $0$. For example, $psi ([ 1, 1 ]) = 2$ because you can negate the first element and the array will then be $[ -1, 1 ]$ which has a sum of $0$ or you can negate the second element making the array $[ 1, -1 ]$ which also has a sum of $0$.
Given an array $A$ of $n$ positive integers, let $S$ be the set of all contiguous, non-empty subarrays of $A$ (aka all arrays of the form $a_i, a_{i + 1}, \\dots a_j$ where $1 <= i <= j <= n$ where two subarrays are considered different if they start and/or end at different indices, even if the values within the subarray are the same), compute the sum of $psi (x)$ for all $x in S$ aka $sum limits_{x in S} psi (x)$.
Note this number may be very large, so print it modulo $10^9 + 7$.
The first line will contain a single integer $n$, representing the number of elements in the array ($1 <= n <= 1000$).
The second line will contain $n$ space-separated positive integers, $a_1, a_2, \\dots, a_n$ where $1 <= a_i <= 1000$. It is also guaranteed that $a_1 + a_2 + \\dots + a_n <= 10000$.
Output a single integer, the sum modulo $10^9 + 7$ of $psi (x)$ for all $x in S$ where $S$ is the set of all contiguous, non-empty subarrays of the initial array.
## Input
The first line will contain a single integer $n$, representing the number of elements in the array ($1 <= n <= 1000$).The second line will contain $n$ space-separated positive integers, $a_1, a_2, \\dots, a_n$ where $1 <= a_i <= 1000$. It is also guaranteed that $a_1 + a_2 + \\dots + a_n <= 10000$.
## Output
Output a single integer, the sum modulo $10^9 + 7$ of $psi (x)$ for all $x in S$ where $S$ is the set of all contiguous, non-empty subarrays of the initial array.
[samples]
**Definitions**
Let $ s $ be a string of length $ n $ over alphabet $ \Sigma = \{a, b, \dots, z\} $.
Let $ p_\sigma \in \mathbb{Z}^+ $ be the weight for character $ \sigma \in \Sigma $, with total weight $ P = \sum_{\sigma \in \Sigma} p_\sigma $.
The probability of typing $ \sigma $ is $ \frac{p_\sigma}{P} $, independently at each keystroke.
For any nonempty substring $ t $ of $ s $, let $ E(t) $ denote the expected number of keystrokes until $ t $ first appears as a contiguous substring in the random string generated by the monkey.
**Constraints**
- $ 1 \leq n \leq 5 \times 10^5 $
- $ 1 \leq p_\sigma \leq 5 \times 10^5 $ for all $ \sigma \in \Sigma $
- All operations are modulo $ M = 10^9 + 7 $
**Objective**
Compute:
$$
\sum_{t \text{ is a substring of } s} E(t) \mod M
$$