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.
## Input
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.
## Output
Print a single integer, the number of mappings of digits to directions that will lead the robot to the exit.
[samples]
## Note
For the first sample, the only valid mapping is , where _D_ is down, _L_ is left, _U_ is up, _R_ is right.
**Definitions**
Let $ n, m \in \mathbb{Z} $ be the dimensions of the maze.
Let $ M \in \{\text{.}, \#, S, E\}^{n \times m} $ be the maze grid.
Let $ (s_r, s_c) \in \{1, \dots, n\} \times \{1, \dots, m\} $ be the unique start position where $ M[s_r][s_c] = S $.
Let $ (e_r, e_c) \in \{1, \dots, n\} \times \{1, \dots, m\} $ be the unique exit position where $ M[e_r][e_c] = E $.
Let $ s \in \{0,1,2,3\}^* $ be the instruction string, with $ |s| = L $.
Let $ \mathcal{D} = \{ \text{up}, \text{down}, \text{left}, \text{right} \} $ be the set of four cardinal directions.
Let $ \Pi $ be the set of all bijections $ \pi: \{0,1,2,3\} \to \mathcal{D} $; $ |\Pi| = 4! = 24 $.
For a mapping $ \pi \in \Pi $, define the robot’s trajectory $ (x_0, y_0), (x_1, y_1), \dots, (x_L, y_L) $ as:
- $ (x_0, y_0) = (s_r, s_c) $
- For $ i = 1 $ to $ L $:
Let $ d = \pi(s[i-1]) $
Let $ (x_i, y_i) = (x_{i-1}, y_{i-1}) + \vec{v}_d $, where $ \vec{v}_d $ is the unit vector for direction $ d $:
- $ \text{up}: (-1, 0) $, $ \text{down}: (1, 0) $, $ \text{left}: (0, -1) $, $ \text{right}: (0, 1) $
If $ (x_i, y_i) $ is out of bounds or $ M[x_i][y_i] = \# $, the trajectory **crashes** at step $ i $.
If $ (x_i, y_i) = (e_r, e_c) $, the trajectory **succeeds** and stops.
**Constraints**
1. $ 2 \le n, m \le 50 $
2. $ 1 \le |s| \le 100 $
3. Exactly one $ S $ and one $ E $ in $ M $
4. $ S, E \neq \# $
**Objective**
Count the number of mappings $ \pi \in \Pi $ such that the robot’s trajectory under $ \pi $:
- Does **not crash** at any step, and
- Reaches $ (e_r, e_c) $ at some step $ i \le L $.