C. 机器人走迷宫

有一个 n×m 个单元格构成的迷宫，其中空单元格用 . 表示，障碍物用 # 表示。

迷宫中有一个机器人，它的起点位置用 S 表示，目标位置用 E 表示，这两个地点均没有障碍。

机器人只能沿上下左右四个方向移动。

给定一串由数字 0∼3 构成的字符串，表示机器人的行动指令列表。

机器人将按照列表中的指令，依次进行移动。

在执行指令的过程中：

• 如果机器人走出迷宫边界或者碰到障碍物，则机器人会损坏。
• 如果机器人到达目标位置，则停止行动，不再接受后续指令。

现在，哪个数字（0∼3）对应哪种行动（上下左右）还未分配。

请问，共有多少种分配方案，能够使得机器人顺利到达目标位置。

第一行包含整数 T，表示共有 T 组测试数据。

每组数据第一行包含两个整数 n 和 m。

接下来 n 行，每行包含 m 个字符，表示迷宫。所有字符均为 ., #, S, E 之一，其中 S 和 E 出现且仅出现一次。

最后一行包含一个字符串 s 表示指令列表，每个字符均为 0∼3 之一。

每组数据输出一行结果，表示能够使得机器人顺利到达目标位置的行动指令分配方案数量。

输入样例：

2
5 6
.....#
S....#
.#....
.#....
...E..
333300012
6 6
......
......
..SE..
......
......
......
01232123212302123021

输出样例：

1
14

前三个测试点满足 2≤n,m≤10。

所有测试点满足 1≤T≤10，2≤n,m≤50，1≤|s|≤100。

同一测试点内，所有 n×m 的和不超过 2500。