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 $998\, 244\, 353$.


The single line of input contains two space-separated integers $r$ and $c$ $(1 \leq r,c\leq 50)$, where $r$ is the number of rows in Eddy’s garden grid, and $c$ is the number of columns.


Output a single integer, which is the number of ways Eddy can place plants in his garden, modulo $998\, 244\, 353$.

Sample Input 1 Sample Output 1
3 2
Sample Input 2 Sample Output 2
1 5
Sample Input 3 Sample Output 3
42 25

Please log in to submit a solution to this problem

Log in