You have an chessboard. An -leaper is a chess piece which can move from some square to some square if ; however, its movements are restricted to up (), down (), left (), and right () within the confines of the chessboard, meaning that diagonal moves are not allowed. In addition, the leaper cannot leap to any square that is occupied by a pawn.
Given the layout of the chessboard, can you determine the number of ways a leaper can move times within the chessboard?
Note: refers to the absolute value of some integer, .
The first line contains an integer, , denoting the number of queries. Each query is described as follows:
The first line contains three space-separated integers denoting , , and , respectively.
Each line of the subsequent lines contains characters. The character in the line describes the contents of square according to the following key:
. indicates the location is empty.
P indicates the location is occupied by a pawn.
L indicates the location of the leaper.
There will be exactly one L character on the chessboard.
The -leaper can move up (), down (), left (), and right () within the confines of the chessboard. It cannot move diagonally.
For each query, print the number of ways the leaper can make moves on a new line. Because this value can be quite large, your answer must be modulo .