possible moves for two knights
Thanks to Clive Fraser for creating this problem!
We have a chess board with dimensions W x H, so there are W*H squares on the board. We also have three
knights which are placed on different squares on the board. These are standard chess pieces so they make the
usual knight's move. One of the knights is black and the other two are white. A knight is said to be in an
attacking position if there is a knight of the opposite colour which is exactly one knight's move away
(in other words it can be captured in 1 move). The black knight can be in an attacking position with respect
to either or both of the white knights. Similarly, either or both of the white knights can be in an attacking
position with respect to the black knight. However, since the two white knights are on the same team, they can
never be in attacking positions with respect to each other, even if they are exactly one knight's move apart.
Knight move in Chess consists of changing coordinate by 2 squares horizontally and 1 vertically or
vice versa, by 1 cells horizontally and 2 vertically. Knight could not be blocked by any
adjacent piece in Western Chess, so 8 squares are available for move except those which lie outside the board
or those which contain same-color pieces. (more info in wikipedia article)
In this problem we have three friendly knights. This means that none of the knights is in an attacking position. You are asked to find the number of different arrangements of the three knights on the given board so that all three knights are in friendly (non-attacking) positions. Note that the two white knights are indistinguishable, so swapping their positions does not give rise to a new arrangement.
The boards are all rectangular in shape but the shape can vary from a square to a narrow strip. All board sizes
will contain at least 100 squares. If we consider a very small board of size 3 x 2, it is easy to verify
(with pencil and paper) that there are 44 different arrangements of the three friendly knights. Note that this
example is much smaller than the boards in the actual problem.
The number of arrangements rises rapidly as the board size increases. Because of this you are asked to give your
answer modulo 1000000007 (10^9 +7).
Input/Output description: The first line of the input data will be a single integer N for the number of
puzzles to be solved. N lines will follow. Each line will contain two space-separated integers W and H,
giving the width and height of the chessboard. For each puzzle you must calculate the number of different ways
of placing the three friendly knights on the board. Give all answers (modulo 1000000007), separated by spaces,
as a single string.
Example:
input:
4
2 50
29 37
50 50
1234 2141
answer:
466376 607625308 756188247 942240451