Number of paths in a grid 2
Given a grid of height
h and width w, you are asked to calculate the number of unique paths one can take to move from the top-left corner to the bottom-right corner. You’re only allowed to move right, down, and diagonally in the bottom-right direction.o | ➡️ | ㅤ | ㅤ |
⬇️ | ↘ | ㅤ | ㅤ |
ㅤ | ㅤ | ㅤ | x |
Input
The input contains two integers
h and w (1 ≤ h, w ≤ 100).Output
The program should print the number of unique paths it’s possible to take from the top-left to the bottom-right corner of the grid. The output can be large, so the answer should be taken modulo .
Examples
Input | Output |
2 3 | 5 |
3 4 | 25 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB