After finally distinguishing between the chess pieces, Shane is now learning how the pieces move!
He finds all the pieces simple enough, except for the knight.
However, 3 of the 4 knights in his chess set have been compromised as part of Fred's knight fork experiment. Therefore, he is left with a single knight to test out.
He places his knight on the upper-left most corner, and proceeds to make moves in an attempt to reach the bottom right corner. However, he quickly realises it is impossible on an 8x8 square without moving it back up or to the left at some point. He wonders what the dimensions of a board would have to be to allow the knight to reach the bottom-right corner without requiring such a move.
Can you write a chess engine to solve Shane's problem?
For his experiment, Shane may only move the knight from a cell to cells or . The knight must also stay on the board.
Python users are reccomended to submit in PyPy.
Constraints
Subtask 1 [30%]
Subtask 2 [70%]
Input Specification
The first and only line of input contain the dimensions of the rectangular board, and .
Ouput Specification
Output one integer, the number of ways for a knight to move from the top-left corner to the bottom-right corner while following the rules. As the answer may be very large, output the answer modulo .
Sample Input 1
3 2
Sample Output 1
1
Sample Input 2
10 10
Sample Output 2
20
Sample Input 3
2999 3000
Sample Output 3
36237869
Comments