Problem D: Dash to Vince

Problem D: Dash to Vince

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 401  Solved: 166
[Submit][Status][Web Board]

Description

Yee_172 is in a maze of n row and m columns. He is in position S and he wants to go to position V since he wants to find his friend Vince. Vince has told Yee_172 how to find position E by giving Yee_172 a sequence of directions: 01123321……. It confuses Yee_172 because Vince only told him that 0123 means four directions, but not specifically up, left, right, or down. (i.e. the mappings relationship between the digits and specific directions are unknown)
Therefore, Yee_172 turns for your help. You need to calculate the number of mappings of digits to directions that will lead Yee_172 to Vince. 

Input

The first line is T, which is the number of test cases, (T <= 10);
For each test case, the first line will be integer n, m, and then n lines following, each line contains m characters (‘#’ means a beautiful girl, if Yee_172 go to ‘#’, he will stop finding Vince, ‘S’ is the start point and ‘E’ is Vince point.) N, m <= 50;
After the n lines, there will be one line contains 0, 1, 2, 3 only, meaning the sequence Yee have, which has a length of no more than 100.

Output

For each test case, print a single integer, which the number of directions permutation that leads the Yee_172 to the Vince. 

Sample Input

2
5 6
.....#
S....#
.#....
.#....
...E..
333300012
5 3
...
.S.
###
.E.
...
3

Sample Output

1
0

HINT

[Submit][Status]