We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Fairy Chess

Fairy Chess

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:

  1. The first line contains three space-separated integers denoting , , and , respectively.
  2. 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.

Constraints

  • 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.

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 .

  1. The leaper can leap to the following locations:
    q_0
    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.
  2. The leaper can leap to the following locations:
    q_1
    Thus, we print on a new line.

Note: Don't forget that your answer must be modulo .