## A Math Contest P14 - Choosing Marbles

View as PDF

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

Author:
Problem type

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.

#### 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: