City Road Division

In a newly built city (which can be seen as a connected region of the plane), you are given several types of roads that will be constructed in order to partition the city into as many disconnected regions as possible.

The construction is as follows:

• First, build a₁ main roads. A main road is modeled as an infinite straight line that crosses the entire city.
• Next, build a₂ ring roads. A ring road is modeled as a circle (a closed convex curve).
• Then, build road networks in the shapes of convex regular polygons: a₃ triangular roads (an equilateral triangle is a simple closed convex curve), a₄ quadrilateral roads, …, up to a_n regular n-gon roads.

All roads are constructed in such a way that they are in general position; that is, no three roads cross at a single point and any two curves intersect at the maximum possible number of points. In particular:

• Two distinct straight lines intersect in at most 1 point.
• A straight line and any closed convex curve (circle or convex polygon) can intersect in at most 2 points.
• Two distinct closed convex curves can intersect in at most 2 points.

The goal is to compute the maximum number of disconnected (non‐communicating) regions into which the city can be partitioned using the given roads. Since the answer can be very large, output it modulo \(10^9+7\).

How to compute?

Let \(L = a_1\) be the number of lines and let \(P = a_2 + a_3 + \cdots + a_n\) be the total number of closed curves. The following strategy yields the maximum number of regions:

1. The \(L\) lines, when placed in general position, divide the plane into \(\dfrac{L(L+1)}{2} + 1\) regions.
2. Each new closed curve, when added one by one in general position, will be intersected by all previously drawn roads. In particular, for the first closed curve:
   • If there is at least one line (\(L > 0\)), it can intersect all those lines in \(2L\) points and thus add \(2L\) regions.
   • If \(L = 0\), since there is no intersection, a single closed curve divides the plane into 2 regions (an addition of 1 region on top of the 1 initial region).
3. For the \(k\)-th closed curve (with \(2 \le k \le P\)), it can intersect all the \(L\) lines in \(2L\) points and all the previous \(k-1\) closed curves in \(2(k-1)\) points. Thus, it creates \(2L + 2(k-1)\) new regions.

Thus, the total number of regions \(R\) is given by:

If \(P = 0\): \[ R = \frac{L(L+1)}{2} + 1. \]

If \(P \ge 1\): \[ R = \frac{L(L+1)}{2} + 1 + \Bigl(\Delta_1 + \sum_{k=2}^{P} \bigl[2L + 2(k-1)\bigr]\Bigr), \]

where \(\Delta_1 = \begin{cases} 2L, & \text{if } L > 0, \\ 1, & \text{if } L = 0. \end{cases}\)

Simplifying the summation for \(k\) from 2 to \(P\): \[ \sum_{k=2}^{P} \bigl[2L + 2(k-1)\bigr] = 2L(P-1) + 2\cdot\frac{(P-1)P}{2} = 2L(P-1) + P(P-1). \]

Hence, if \(L > 0\): \[ R = \frac{L(L+1)}{2} + 1 + 2L P + P(P-1), \]

and if \(L = 0\): \[ R = 1 + 1 + P(P-1) = 2 + P(P-1). \]

You are to read the input, compute \(R\) as defined above and output \(R \bmod (10^9+7)\).

inputFormat

The first line of input contains a single integer n (\(1 \le n \le 10^5\)), representing the number of different road types. Then follows a line containing n space‐separated non-negative integers: \(a_1, a_2, \ldots, a_n\). Here, \(a_1\) is the number of main roads (lines), \(a_2\) is the number of ring roads (circles), and for \(i \ge 3\), \(a_i\) is the number of regular \(i\)-gon roads. It is guaranteed that the sum of all \(a_i\) does not exceed \(10^5\).

outputFormat

Output a single integer, the maximum number of regions (disconnected areas) modulo \(10^9+7\).

sample

1
3

7