There are colours of marbles labelled from
to
with
marbles of colour
.
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
.
Valid ways are considered different if at least one person takes a different marble, even of the same colour.
Constraints
Subtask 1 [5%]
Subtask 2 [15%]
Subtask 3 [80%]
No additional constraints.
Input Specification
The first line contains two space-separated integers, and
.
The next line contains space-separated integers,
.
Output Specification
Output the number of valid ways to choose marbles, modulo .
Sample Input
2 3
1 2 1
Sample Output
10
Explanation for Sample
Let denote the
-th marble of colour
,
denote the
-th marble of colour
, and
denote the
-th marble of colour
.
The ten ways for two people to choose marbles are:
Comments