Problem G
Rampant Growth
Eddy is planning his garden, which can be represented as a grid. He wants his garden to have exactly one plant in each column. To make sure that plants do not compete for resources, if two plants are in adjacent columns, they must be in different rows.
Compute the number of different ways he can place plants in
his garden to respect the above conditions. Two ways are
different if one square has a plant in one arrangement but does
not have a plant in the other. Because the number of ways may
be large, output the number of ways modulo
Input
The single line of input contains two space-separated
integers
Output
Output a single integer, which is the number of ways Eddy
can place plants in his garden, modulo
Sample Input 1 | Sample Output 1 |
---|---|
3 2 |
6 |
Sample Input 2 | Sample Output 2 |
---|---|
1 5 |
0 |
Sample Input 3 | Sample Output 3 |
---|---|
42 25 |
722210361 |