Not Quite Lee
Contest: Codeforces Global Round 17
Difficulty rating: 2000
Tags: combinatorics, dp, math, number theory

Lee couldn't sleep lately, because he had nightmares. In one of his nightmares (which was about an unbalanced global round), he decided to fight back and propose a problem below (which you should solve) to balance the round, hopefully setting him free from the nightmares.

A non-empty array $$$b_1, b_2, \ldots, b_m$$$ is called good, if there exist $$$m$$$ integer sequences which satisfy the following properties:

- The $$$i$$$-th sequence consists of $$$b_i$$$ consecutive integers (for example if $$$b_i = 3$$$ then the $$$i$$$-th sequence can be $$$(-1, 0, 1)$$$ or $$$(-5, -4, -3)$$$ but not $$$(0, -1, 1)$$$ or $$$(1, 2, 3, 4)$$$).
- Assuming the sum of integers in the $$$i$$$-th sequence is $$$sum_i$$$, we want $$$sum_1 + sum_2 + \ldots + sum_m$$$ to be equal to $$$0$$$.

You are given an array $$$a_1, a_2, \ldots, a_n$$$. It has $$$2^n - 1$$$ nonempty subsequences. Find how many of them are good.

As this number can be very large, output it modulo $$$10^9 + 7$$$.

An array $$$c$$$ is a subsequence of an array $$$d$$$ if $$$c$$$ can be obtained from $$$d$$$ by deletion of several (possibly, zero or all) elements.

Input format:
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the size of array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — elements of the array.

Output format:
Print a single integer — the number of nonempty good subsequences of $$$a$$$, modulo $$$10^9 + 7$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
For the first test, two examples of good subsequences are $$$[2, 7]$$$ and $$$[2, 2, 4, 7]$$$:

For $$$b = [2, 7]$$$ we can use $$$(-3, -4)$$$ as the first sequence and $$$(-2, -1, \ldots, 4)$$$ as the second. Note that subsequence $$$[2, 7]$$$ appears twice in $$$[2, 2, 4, 7]$$$, so we have to count it twice.

Green circles denote $$$(-3, -4)$$$ and orange squares denote $$$(-2, -1, \ldots, 4)$$$.

For $$$b = [2, 2, 4, 7]$$$ the following sequences would satisfy the properties: $$$(-1, 0)$$$, $$$(-3, -2)$$$, $$$(0, 1, 2, 3)$$$ and $$$(-3, -2, \ldots, 3)$$$

Example input:
4
2 2 4 7

Example output:
10

Example input:
10
12391240 103904 1000000000 4142834 12039 142035823 1032840 49932183 230194823 984293123

Example output:
996

Editorial:
$$$\mathcal Complete\;\mathcal Solution$$$:
$$$\textbf{I encourage you to read the Hints and Assumptions before reading this.}$$$
Assume we have an array $$$c$$$ of length $$$k$$$, need to know if it's good or not. We can choose an initial sequence $$$t_i$$$ for all $$$1 \le i \le k$$$, then slide them (in other words, choose an index $$$i$$$ and increase or decrease all the elements in the $$$i$$$-th sequence, keep doing this as many times as you need) that way we can reach any other possible set of sequences that satisfy the first property, so it doesn't matter what we choose as initial sequences, because from any set of $$$k$$$ sequences that satisfy the first property, we can reach any other such set of $$$k$$$ sequences.
After that, if $$$\displaystyle \sum_{i = 1}^k sum_i = s$$$, we want to find such $$$x_i$$$-s that $$$\displaystyle \sum_{i=1}^kx_ic_i = -su $$$ so after sliding $$$i$$$-th sequence $$$|x_i|$$$ times to the right(or left if $$$x_i$$$ is negative) for all $$$i$$$, we will have a set of sequences that satisfy both the properties.
Now to do that, one can prove if $$$\displaystyle gcd(c_1, c_2, \ldots, c_k) = g$$$, then if $$$g$$$ divides $$$s$$$, the array is good, otherwise it's not (I won't prove it because it's quite well-known and easy).
If we choose the initial sequences such that the $$$i$$$-th sequence starts from $$$0$$$ and ends with $$$c_i-1$$$, then $$$\displaystyle s = \sum_{i=1}^k \frac{c_i(c_i-1)}2$$$. Now we want $$$g$$$ to divide $$$s$$$. If $$$g$$$ is odd, then it will always divide $$$s$$$ because it divides $$$\frac{c_i}2$$$. From now on we assume $$$g$$$ to be even.
One can prove that if $$$2^l$$$ divides $$$g$$$ and $$$0 < l$$$ is maximum such integer, then $$$\frac g{2^l}$$$ (which is odd) divides all $$$\frac{c_i}2$$$, so $$$s$$$ is divisible by $$$\frac g{2^l}$$$. So we should only check if $$$2^l$$$ also divides $$$s$$$ or not.
If $$$2^{l+1}$$$ divides some $$$c_i$$$, then $$$2^l$$$ divides $$$\frac{c_i(c_i-1)}2$$$ for that $$$i$$$ as well. Also if $$$2^{l+1}$$$ doesn't divide $$$c_i$$$, we knew that $$$2^l$$$ divides $$$c_i$$$ (because $$$2^l$$$ divides $$$g$$$ and $$$g$$$ divides $$$c_i$$$) so $$$2^{l-1}$$$ divides $$$\frac{c_i}2$$$ but $$$2^l$$$ doesn't, also $$$c_i-1$$$ is odd. So $$$\frac{c_i(c_i-1)}2$$$ has a reminder equal to $$$2^{l-1}$$$ modulo $$$2^l$$$. All the other terms $$$\frac{c_i(c_i-1)}2$$$ were divisible by $$$2^l$$$ except these, so if the number of such $$$c_i$$$-s is even, then their reminders sum up to $$$0$$$ modulo $$$2^l$$$ then $$$c$$$ is good, and not otherwise.
To solve the actual problem, we can fix $$$l$$$, maximum power of 2 that divides $$$g$$$, now we only care about how many $$$c_i$$$-s are divisible by $$$2^l$$$ (let's say $$$x$$$ such $$$c_i$$$-s, also if $$$x < 2$$$ then we should skip this $$$l$$$ because we need at least $$$2$$$ such $$$c_i$$$-s to have an array with that $$$l$$$), and how many are divisible by $$$2^{l+1}$$$ (let's say $$$y$$$ such $$$c_i$$$-s).
Now there are $$$2^x$$$ possible subsequences such that $$$2^l$$$ divides $$$g$$$ (including the empty subsequence), but some of them may have an odd number of $$$c_i$$$-s not divisible by $$$2^{l+1}$$$, it's easy to see that half of them have an even number of such $$$c_i$$$-s, still, for $$$2^y$$$ of them, $$$2^{l+1}$$$ divides $$$g$$$ as well (which is not what we want. Also includes the empty subsequence). So we have $$$2^{x-1}-2^y$$$ subsequences with that $$$l$$$ (doesn't include the empty subsequence).
Then we sum up this for all possible $$$l$$$, also don't forget to count $$$l=0$$$ separately (i.e. $$$g$$$ is odd).
Time complexity: $$$\mathcal{O}(nlog(10^9))$$$