407560: GYM102829 G Contrived Array Property

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 \leq i \leq j \leq 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 \leq n \leq 1000$$$).

The second line will contain $$$n$$$ space-separated positive integers, $$$a_1, a_2, \dots, a_n$$$ where $$$1 \leq a_i \leq 1000$$$. It is also guaranteed that $$$a_1 + a_2 + \dots + a_n \leq 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.

3
1 2 1

2

4
1 1 1 1

12