M. Tea Party
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

After the UTPC officers arrived in their final stop at Boston, Randy decides to participate in the annual Boston Tea Party, where he will be dumping boxes of tea into the Boston harbor.

Currently, Randy has $$$n$$$ boxes of tea lined up to be dumped, with the $$$i$$$th box weighing $$$w_i$$$ pounds. On the $$$i$$$th second after the party has commenced, Randy can either dump the $$$i$$$th box into the harbor or choose not to do anything.

Since the organizers of the party are concerned about the environmental consequences of dumping tea, they have imposed the following restriction: At any given moment, the amount of tea a person can dump cannot exceed $$$t^2$$$ pounds in total (since the party started), where $$$t$$$ is the number of seconds after the party has begun.

As Randy wants to be well prepared for this momentous event, he would like to know the number of ways he can dump tea into the harbor without violating the party rules. Two ways of dumping tea are considered distinct if there exists a box that was dumped in one way but not the other.

Input

The first line contains $$$n$$$ $$$(1 \le n \le 10^5)$$$ — the number of tea boxes Randy has.

The second line contains $$$n$$$ integers $$$w_1, w_2,\dots,w_n$$$ $$$(0 \le w_i \le 10^5)$$$ — the weights of the boxes. It is guaranteed that $$$\sum_{i=1}^n w_i \le 10^5$$$.

Output

Output a single integer, the number of ways Randy can dump tea into the harbor. Since the answer may be large, output it modulo $$$10^9 + 7$$$.

Examples
Input
2
1 4
Output
3
Input
3
3 3 3
Output
4
Note

In the first test case, Randy can dump tea into the harbor in three ways:

  1. Do nothing.
  2. Dump only the first box.
  3. Dump only the second box.

In the second test case, Randy can dump tea into the harbor in four ways:

  1. Do nothing.
  2. Dump only the second box.
  3. Dump the second box and the third box.
  4. Dump only the third box.