Background

Xiao Ju has established a city. With his excellent (or rather, mediocre) political skills, he manages and plans the city.

Problem Description

For a newly built city, it can be considered as a connected area.

Now, Xiao Ju needs to build some roads to divide the city into several disjoint areas.

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

Next, Xiao Ju will build $a_2$ roundabouts. A roundabout is a circular road that connects back to itself.

Then, Xiao Ju will build some road networks. These networks include $a_3$ triangular roads (i.e., three roads forming a closed triangle), $a_4$ square roads... up to $a_n$ regular $n$-sided roads.

Xiao Ju wants to use these roads to divide the city into as many disjoint areas as possible. However, he does not know how to calculate the maximum number of areas, so he comes to you for help.

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

Input Format

The first line contains a positive integer $n$, representing the highest number of sides in the road networks in Xiao Ju's plan.

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

Output Format

A single line containing an integer, representing the answer modulo $10^9+7$.

Sample Input and Output

Sample Input #1

4
1 1 1 1

Sample Output #1

28

Sample Input #2

3
1 2 3

Sample Output #2

68

Notes

Sample Explanation #1

As shown in the following image:

Data Range

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

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

Note the memory limit; your solution is likely to exceed memory limits (MLE).

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

见题面 Input 部分

见题面 Output 部分