LCC '22 Contest 5 J4 - Stonkfish

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 512M

Author:
Problem type

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 (x, y) to cells (x + 1, y + 2) or (x + 2, y + 1). The knight must also stay on the board.

Python users are reccomended to submit in PyPy.

Constraints

Subtask 1 [30%]

1 \le l, w \le 10

Subtask 2 [70%]

1 \le l, w \le 10^4

Input Specification

The first and only line of input contain the dimensions of the rectangular board, l and w.

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 10^9+7.

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

There are no comments at the moment.