Problem G
Restaurant Rinser
Sanna the sanitiser is working the closing shift at the nearby fast food shop, and has the responsibility of cleaning all the tables. She wants to get home early and has used her knowledge of electronics and cybernetics to construct a robot that can clean tables for her! Unfortunately, she has not yet had time to program the planning algorithm which would make it go directly to the dirty tables, so for now it wanders around aimlessly cleaning everything it encounters.
The robot can move around the restuarant, which is a grid of tables. For every time step, the robot moves to one of the neighboring tables and cleans it. Since there is no planning involved, it moves to a random neighboring table! It can move in all four directions, but it will avoid walking into walls. Sanna is almost done cleaning the tables, and turns on the robot when there is exactly one dirty table left, hoping that it will clean it during the night. Help her figure out how what fraction of the possible paths the robot could take would end up cleaning the last dirty table. To be clear, we are asking about what fraction of all possible the robot could take would leave the restaurant clean, not the probability of it happening.
Input
The first line of input contains $T$, the number of timesteps the robot will complete during the night, and $L$, the length and width of the grid of tables. The next $L$ lines each contain a string of $L$ characters. The characters can be either “C”, meaning that the table is clean, “D”, meaning that the table is dirty, or “S”, meaning it is the starting position of the robot. There will be exactly one “S” and one “D” in the input.
Output
Output the fraction of possible paths the robot could take that would end up cleaning the last dirty table. Since the numerator and denominator can be very large the answer should be given modulo $1\, 000\, 000\, 007$. This means the answer should be equivalent to $\frac{A}{B}$ in modular arithmetic terms, where $A$ is the total number of valid paths that clean up the last table, and $B$ is the total number of valid paths. Since we are working modulo $1\, 000\, 000\, 007$, the answer should be $A \cdot B^{-1}$, where $B^{-1}$ is the multiplicative inverse of $B$ in this modulus. The test data guarantees that this multiplicative inverse exists.
Limits
-
$1 \leq T \leq 1000$
-
$2 \leq L \leq 200$
| Sample Input 1 | Sample Output 1 |
|---|---|
5 3 CCD CCC SCC |
843750006 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 4 DCCS CCCC CCCC CCCC |
0 |
