You are at the origin in the N-dimensional plane and want to go some point in the plane in the minimum number of steps. Formally, with every step you take, you must decrease the distance between you and the end place by one.

If you are provided with the endpoint, calculate the number of different ways you can go to the endpoint mod $$10^9 + 7$$.

Input format

• The first line contains $n$.
• The second line contains $n$ integers denoting the coordinate of the destination.

Output format

Print the number of ways you can reach the destination mod $$10^9 + 7$$.

Constraints

$$1 \le t \le 50$$

$$1 \le n \le 10^5$$

It is guaranteed that the minimum distance that will be moved from origin to endpoint will be less than or equal to $$2*10^5$$.