Problem I
Ghostbusters 3
There is something strange in the neighbourhood. Who you gonna call? Ghostbusters!
A number of ghosts have decided to roam the street, and the Ghostbusters have arrived to deal with this situation. Luckily all the ghosts have decided to stay on one side of a very long street, so it is safe for the Ghostbusters to stand on the opposite side of the street to aim and fire their particle beams at the ghosts. Each Ghostbuster must aim at exactly one ghost, and it is important that the beams do not cross. Two beams are not considered to be crossing each other if they are both aimed at the same ghost.
How many ways are there to assign ghosts to the
Ghostbusters, so that as many ghosts as possible are assigned
to some Ghostbuster? Of course, no two beams can cross each
other. As the answer may be very large, please report the
answer modulo
Input
There is one line of input containing two integers,
Output
Output the total number of ways ghosts can be assigned to
Ghostbusters as described in the problem statement, modulo
Sample Input 1 | Sample Output 1 |
---|---|
2 5 |
10 |
Sample Input 2 | Sample Output 2 |
---|---|
3 3 |
1 |
Sample Input 3 | Sample Output 3 |
---|---|
5 2 |
4 |