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.
~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.
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 the number of valid ways to choose marbles, modulo ~10^9+7~.
2 3 1 2 1
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~