Задача №112615. Конь-X
Шахматный конь должен пройти по клетчатой доске размером N на M клеток из левого верхнего угла в правый нижний. Из каждой клетки есть четыре возможных хода:
Определите, сколькими способами конь может пройти этот маршрут. Поскольку это число может быть очень велико, вычислите его по модулю 10 6 + 7 , то есть найдите остаток от деления этого числа на 10 6 + 7 .
Входная строка содержит два натуральных числа: размеры доски N и M ( 1 ≤ N , M ≤ 500 ).
Программа должна вывести число возможных маршрутов шахматного коня из левого верхнего угла поля в правый нижний, вычисленное по модулю 10 6 + 7 .
5 5
4