There are $M$ colours of marbles labelled from $1$ to $M$ with $a_i$ marbles of colour $i$ $(1\le i\le M)$. $N$ people will each choose one marble, where no two people can choose the same colour marble. Find how many valid ways they can choose marbles, modulo ${10}^9+7$.

Valid ways are considered different if at least one person takes a different marble, even of the same colour.

Constraints

$1\le N\le M\le 2\times {10}^5$

$1\le a_i\le {10}^9$

Subtask 1 [5%]

$1\le N\le 2$

Subtask 2 [15%]

$1\le N\le M\le 5\times {10}^3$

Subtask 3 [80%]

No additional constraints.

Input Specification

The first line contains two space-separated integers, $N$ and $M$.

The next line contains $M$ space-separated integers, $a_1,a_2,\dots ,a_M$.

Output Specification

Output the number of valid ways to choose marbles, modulo ${10}^9+7$.

Sample Input

2 3
1 2 1

Sample Output

10

Explanation for Sample

Let $x_i$ denote the $i$-th marble of colour $1$, $y_i$ denote the $i$-th marble of colour $2$, and $z_i$ denote the $i$-th marble of colour $3$.

The ten ways for two people to choose marbles are:

• $x_1,y_1$
• $x_1,y_2$
• $x_1,z_1$
• $y_1,z_1$
• $y_2,z_1$
• $y_1,x_1$
• $y_2,x_1$
• $z_1,x_1$
• $z_1,y_1$
• $z_1,y_2$