Let's play Fairy Chess!
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, .
Input Format
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.Pindicates the location is occupied by a pawn.Lindicates the location of the leaper.
Constraints
- There will be exactly one
Lcharacter on the chessboard. - The -leaper can move up (), down (), left (), and right () within the confines of the chessboard. It cannot move diagonally.
Output Format
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 .
Sample Input 0
3
4 1 1
....
.L..
.P..
....
3 2 1
...
...
..L
4 3 2
....
...L
..P.
P...
Sample Output 0
4
11
385
Explanation 0
You must perform two queries, outlined below. The green cells denote a cell that was leaped to by the leaper, and coordinates are defined as .
- The leaper can leap to the following locations:
Observe that the leaper cannot leap to the square directly underneath it because it's occupied by a pawn. Thus, there are ways to make move and we print on a new line. - The leaper can leap to the following locations:
Thus, we print on a new line.
Note: Don't forget that your answer must be modulo .