Description

For a newly built city, we can treat it as one connected region.

Now, Xiao Ju needs to build some roads to divide the city into several regions that are disconnected from each other.

First, Xiao Ju will build $a_1$ trunk roads. A trunk road is a straight line that goes through the entire city.

Next, Xiao Ju will build $a_2$ roundabouts. A roundabout is a circular road whose start and end connect together.

Then, Xiao Ju will build some road networks. These road networks include $a_3$ regular triangle roads (that is, three roads form a closed triangle), $a_4$ regular quadrilateral roads, $\ldots$, and $a_n$ regular $n$-gon roads.

Xiao Ju wants to use these roads to partition the city into as many disconnected regions as possible. But he cannot compute the maximum number of regions, so he asks you for help.

Since the final answer may be extremely large, you only need to output the answer modulo $10^9+7$.

Input Format

The first line contains a positive integer $n$, meaning that in Xiao Ju’s plan, the road network with the largest number of sides is an $n$-gon.

The second line contains $n$ integers, which are $a_{1\dots n}$.

Output Format

Output one integer per line, the answer modulo $10^9+7$.

4
1 1 1 1

28

3
1 2 3

68

Hint

Sample Explanation #1

As shown in the figure below:

Constraints

For $20\%$ of the testdata: $1\le n \le 10^3$, $0 \le a_i \le 100$.

For $100\%$ of the testdata: $1\le n \le 3 \times 10^6$, $0 \le a_i \le 10^3$.

Note the memory limit: your UKE is very likely to get MLE.

If $n=1$, then only straight roads exist. If $n=2$, then only straight roads and circular roads exist.

Translated by ChatGPT 5