Michael's robot is trapped in a maze! The maze is a $$$n\times m$$$ rectangular grid, in which there are some obstacles that the robot cannot pass. Initially, the robot is on $$$(1,1)$$$ of the maze. Fortunately, he can command his robot using a string $$$S$$$ of length $$$K$$$. On the $$$i$$$-th move,
However, his robot fails to receive all his commands! In the string $$$S$$$ received by the robot, if $$$S_i$$$ is a "?", the robot doesn't know the exact command. Find the number of ways the robot can follow the command without hitting an obstacle or leaving the maze. Since the answer can be large, output the answer $$$\pmod{10^9+ 7}$$$.
The first line contains three integers $$$n,m,K$$$ $$$(1\le n,m,K\le 5000)$$$, representing the size of the maze and the length of Michael's command.
For the next $$$n$$$ lines, the $$$i$$$-th line includes a single string $$$A_i$$$, representing the $$$i$$$-th row of the maze. If $$$A_{i,j}=$$$"#", the $$$(i,j)$$$-th block of the maze is an obstacle. Otherwise, $$$A_{i,j}=$$$".".
The last line includes a single string $$$S$$$, the command received by Michael's robot. Each of $$$S$$$ letter is either 'R','D', or '?'.
The number of ways the robot can follow the command without hitting an obstacle or leaving the maze $$$\pmod{10^9 + 7}$$$.
3 3 3 ... ... ... ???
6
4 4 4 .##. .#.. .... .... D??D
1
9 7 10 ....... ..##... ......# ..##..# ....... .#..... .....#. ...#... .....## ?D?DD?R?DD
3
In the first example, the six possible commands that the robot may follow are: $$$DDR,DRD,RDD,RRD,RDR$$$, and $$$DRR$$$.
In the second example, the only possible command that the robot may follow is $$$DDRD$$$. In this way, the robot will follow $$$DDRD$$$. It will follow the path:
$$$$$$(1,1)\to(2,1)\to(3,1)\to(3,2)\to(4,2)$$$$$$
