Dexter has you on his kill table now. He gives you one last chance to survive. He gives you a problem to solve. If you solve the problem correctly, he will let you go, else he will kill you.

You are given N integers \(a_1, a_2, ,...,a_N\). Consider an N-dimensional hyperspace. Let \((x_1,x_2,...,x_N)\) be a point in this hyperspace and all \(x_i\) for \(i \in [1,N]\) are integers. Now, Dexter gives you a set which contains all the points such that \(0 \le x_i \le a_i\) for \(i \in [1,N]\). Find the number of ways to select two points A and B from this set, such that the midpoint of A and B also lies in this set.

As the required number can be really large, find the answer modulo \(10^9+7\).

Note: The two selected points can be same.

Input
First line of input contains a single integer N, representing the number of dimensions in the hyperspace. The second line contains N integers, the \(i^{th}\) of them representing \(a_i\), as defined in the problem.

Output
The output contains a single integer, the answer to the problem, modulo \(10^9+7\).

Constraints
\(1 \le N \le 10^5\)
\(0 \le a_i \le 10^9\)