- Prepare
- Algorithms
- Dynamic Programming
- Fairy Chess

# 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:

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

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

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