题目描述

小桃编写了一个程序，让机器人在一个二维迷宫中巡逻。

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

迷宫中机器人的起始位置用字符 S 表示，迷宫出口位置用字符 E 表示。

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

当小桃编写机器人时，他记下了一个由数字 $0$ 到 $3$ 组成的字符串。他打算让每个数字对应一个不同的方向，机器人将按顺序遵循这些方向以到达出口。不幸的是，他忘记了给数字指定方向。

机器人将把不同的数字映射到不同的方向，这个过程是随机的。然后机器人将按照给定字符串中的顺序和选择的映射来执行指令。如果一条指令会导致机器人走出迷宫边缘或撞到障碍物，则机器人将崩溃并停止。如果机器人在任何时候到达出口，则机器人将停止遵循任何进一步的指令。

小桃在调试他的机器人时遇到了麻烦，因此他想确定将机器人走到迷宮出口的数字到方向的映射数量。

输入格式

第一行包含两个整数 $n$ 和 $m$，表示迷宫的尺寸。

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

迷宫的每个字符将是 . , # , S , 或 E 。

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

最后一行包含一个字符串 $s$，表示给机器人的指令，$s$ 仅包含数字 $0$ 到 $3$ 。

输出格式

输出一个整数表示答案。

5 6
.....#
S....#
.#....
.#....
...E..
333300012

1

样例1解释

唯一有效的映射是，其中 D 是向下，L 是向左，U 是向上，R 是向右。

6 6
......
......
..SE..
......
......
......
01232123212302123021

14

5 3
...
.S.
###
.E.
...
3

0

约定与提示

对于100%的数据，$1 \leq n,m \leq 50$，$1 \leq |s| \leq 100$，$|s|$ 表示最后一行的字符串长度 。