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.
Subtask 1 [5%]
Subtask 2 [15%]
Subtask 3 [80%]
No additional constraints.
The first line contains two space-separated integers, and .
The next line contains space-separated integers, .
Output the number of valid ways to choose marbles, modulo .
2 3 1 2 1
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: