A Math Contest P14 - Choosing Marbles

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem type

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.

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


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


There are no comments at the moment.