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~