walks from the bottom-left corner of a
chessboard to the top-right corner. The chessboard contains
horizontal line segments and
vertical line segments. The horizontal line segments are numbered from
to
from bottom to top and the vertical ones are numbered from
to
from left to right. The intersection of horizontal line segment
and vertical segment
is denoted by
%7D)
. The bottom-left corner is
%7D)
and the top-right corner is
%7D)
. At each step, he can only walk from
%7D)
to
%7D)
or from
to
%7D)
.
Each of the
cells is colored white or black. A cell with corners
%2C%20(i%2B1%2Cj)%2C%20(i%2Cj%2B1)%2C%20(i%2B1%2Cj%2B1)%7D)
%7D)
is colored white if and only if
.
Given
's walking path from
to
, his score is
where
is the number of white cells to the left of his walking path and
is the number of black cells to the left of his walking path.
Help
count the number of walking paths with score
modulo
.
--- the number of test cases (
).
).