Количество путей в сетке 2
Дана сетка высотой
h и шириной w. Требуется найти количество уникальных маршрутов, позволяющих перейти из левого верхнего угла сетки в правый нижний. Разрешено перемещаться только вправо, вниз и по диагонали вниз-направо.o | ➡️ | ㅤ | ㅤ |
⬇️ | ↘ | ㅤ | ㅤ |
ㅤ | ㅤ | ㅤ | x |
Входные данные
Во входных данных содержатся два целых числа
h и w (1 ≤ h, w ≤ 100).Выходные данные
Программа должна вывести количество уникальных путей из левого верхнего угла в правый нижний угол. Так как результат может быть очень большим, ответ необходимо вывести по модулю .
Примеры
Input | Output |
2 3 | 5 |
3 4 | 25 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB