You are placed in a \(k-dimensional\) room rather than 3-dimensional room.
Currently, you are positioned at \(\underbrace{(1, 1, 1, \dots , 1)}_\text{k-1's}\). The exit to the room is located at \((x_1, x_2, \dots, x_k)\). There is a strange restriction on movement though, at each step, you can only move in such a way that you increase only one of the k coordinates by one.
For example, from your initial position, you have k choices, you can either go to \((2, 1, 1, \dots, 1)\), \((1, 2, 1, \dots 1)\), \((1, 1, 2, \dots, 1)\) and so on.

Given the coordinates of the exit, you are tasked with finding the number of ways to reach the exit from your initial position as per the restriction.

INPUT

First line contains k - the dimension of the room.

Next line contains k space separated integers where ith integer denotes \(x_i\), the ith coordinate of the exit.

OUTPUT

A single integer denoting the number of ways to reach the exit. Since the answer can be large, output it modulo \(10^9+7\).

CONSTRAINTS

• \(1 \leq k \leq 10^5\)
• \(1 \leq x_i \leq 10^2\)