Problem 1162 -- Dash to Vince ## 1162: 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 ﬁnd his friend Vince. Vince has told Yee_172 how to ﬁnd 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 ﬁrst line is T, which is the number of test cases, (T <= 10);

For each test case, the ﬁrst 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 ﬁnding 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

## Source

[Submit][Status]