Dexter and Points

★★★★★

7 votes

Easy, Greedy Algorithms

Details

Problem

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$

Sample Input

2
1 2

Sample Output

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

The set contains the points:
$\{ (0,0), (0,1),(0,2),(1,0),(1,1),(1,2)\}$ .

The pairs of points(A,B) whose mid point lies in this set are:
$A=(0,0) , B =(0,0), Midpoint =(0,0)$
$A=(0,0) , B=(0,2), Midpoint=(0,1)$
$A=(0,1) , B=(0,1), Midpoint=(0,1)$
$A=(0,2) , B=(0,2), Midpoint=(0,2)$
$A=(0,2) , B=(0,0), Midpoint=(0,1)$
$A=(1,0) , B =(1,0), Midpoint =(1,0)$
$A=(1,0) , B=(1,2), Midpoint=(1,1)$
$A=(1,1) , B=(1,1), Midpoint=(1,1)$
$A=(1,2) , B=(1,2), Midpoint=(1,2)$
$A=(1,2) , B=(1,0), Midpoint=(1,1)$

Contributers:

. .

Satyam Shubham