CF908B.New Year and Buggy Bot

Bob programmed a robot to navigate through a 2d maze.

The maze has some obstacles. Empty cells are denoted by the character '.', where obstacles are denoted by '#'.

There is a single robot in the maze. Its start position is denoted with the character 'S'. This position has no obstacle in it. There is also a single exit in the maze. Its position is denoted with the character 'E'. This position has no obstacle in it.

The robot can only move up, left, right, or down.

When Bob programmed the robot, he wrote down a string of digits consisting of the digits 0 to 3, inclusive. He intended for each digit to correspond to a distinct direction, and the robot would follow the directions in order to reach the exit. Unfortunately, he forgot to actually assign the directions to digits.

The robot will choose some random mapping of digits to distinct directions. The robot will map distinct digits to distinct directions. The robot will then follow the instructions according to the given string in order and chosen mapping. If an instruction would lead the robot to go off the edge of the maze or hit an obstacle, the robot will crash and break down. If the robot reaches the exit at any point, then the robot will stop following any further instructions.

Bob is having trouble debugging his robot, so he would like to determine the number of mappings of digits to directions that would lead the robot to the exit.

鲍勃编写了一个机器人，使其在二维迷宫中导航。

迷宫中存在一些障碍物。空单元格用字符 '.' 表示，障碍物用 '#' 表示。

迷宫中恰好有一个机器人，其起始位置用字符 'S' 表示（该位置没有障碍物）；迷宫中也恰好有一个出口，其位置用字符 'E' 表示（该位置也没有障碍物）。

机器人只能向上、向左、向右或向下移动。

鲍勃在编程机器人时，写下一个由数字 0 到 3（含）组成的字符串。他本意是让每个数字对应一个互不相同的方向，机器人将按字符串中数字的顺序执行指令以抵达出口。但不幸的是，他忘记了实际为这些数字指定对应的方向。

机器人将随机选择一种数字到方向的映射：即把四个不同的数字 0, 1, 2, 3 一一对应地映射到四个不同的方向（上、左、右、下）。然后，机器人将依据给定的数字字符串和所选映射，依次执行指令。若某条指令会使机器人移出迷宫边界或撞上障碍物，则机器人将崩溃损毁；若机器人在执行过程中到达出口，则立即停止执行后续所有指令。

鲍勃在调试机器人时遇到了困难，因此他希望计算出：有多少种数字到方向的映射方式，能使机器人成功抵达出口？

The first line of input will contain two integers n and m (2 ≤ n, m ≤ 50), denoting the dimensions of the maze.

The next n lines will contain exactly m characters each, denoting the maze.

Each character of the maze will be '.', '#', 'S', or 'E'.

There will be exactly one 'S' and exactly one 'E' in the maze.

The last line will contain a single string s (1 ≤ |s| ≤ 100) — the instructions given to the robot. Each character of s is a digit from 0 to 3.

输入的第一行包含两个整数 $n$ 和 $m$（$2 \leq n, m \leq 50$），表示迷宫的尺寸。

接下来的 $n$ 行，每行恰好包含 $m$ 个字符，表示迷宫。

迷宫中的每个字符均为 .、#、S 或 E 中的一个。

迷宫中恰好有一个 S 和一个 E。

最后一行包含一个字符串 $s$（$1 \leq |s| \leq 100$）——即提供给机器人的指令。字符串 $s$ 中的每个字符均为 $0$ 到 $3$ 之间的数字。

Print a single integer, the number of mappings of digits to directions that will lead the robot to the exit.

输出一个整数，表示将数字映射到方向的方案数，使得机器人能够到达出口。

For the first sample, the only valid mapping is , where D is down, L is left, U is up, R is right.

对于第一个样例，唯一有效的映射是 ，其中 D 表示向下，L 表示向左，U 表示向上，R 表示向右。