rows строк и cols столбцов. Строки нумеруются от 1 до rows, столбцы — от 1 до cols, клетка записывается как [строка, столбец].
За один ход ладья переходит в любую другую клетку той же строки или того же столбца (на сколько угодно клеток, перепрыгивать ничего не мешает). Остаться на месте нельзя.
Посчитайте, сколькими способами ладья может пройти из клетки start в клетку finish ровно за moves ходов. Способы различаются последовательностью посещённых клеток; по пути можно проходить через любые клетки, в том числе через start и finish. Ответ может быть очень большим — верните его по модулю 10⁹ + 7.rows=2, cols=3, moves=2, start=[1, 1], finish=[2, 3] → 2
Подходят два маршрута: (1,1) → (1,3) → (2,3) и (1,1) → (2,1) → (2,3).
rows=2, cols=2, moves=2, start=[1, 1], finish=[1, 1] → 2
Можно сходить в (1,2) и вернуться или сходить в (2,1) и вернуться — два маршрута.
rows=4, cols=5, moves=1, start=[2, 2], finish=[3, 4] → 0
Клетки в разных строках и разных столбцах, за один ход туда не попасть.
rows, cols ≤ 10⁹moves ≤ 10⁵len(start) = len(finish) = 2start[0], finish[0] ≤ rowsstart[1], finish[1] ≤ colsrows=2, cols=3, moves=2, start=[1, 1], finish=[2, 3]
2
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 99 тестов на сервере, включая скрытые.