{"raw_statement":[{"iden":"statement","content":"Bob programmed a robot to navigate through a 2d maze.\n\nThe maze has some obstacles. Empty cells are denoted by the character '_._', where obstacles are denoted by '_#_'.\n\nThere 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.\n\nThe robot can only move up, left, right, or down.\n\nWhen 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.\n\nThe 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.\n\nBob 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."},{"iden":"input","content":"The first line of input will contain two integers _n_ and _m_ (2 ≤ _n_, _m_ ≤ 50), denoting the dimensions of the maze.\n\nThe next _n_ lines will contain exactly _m_ characters each, denoting the maze.\n\nEach character of the maze will be '_._', '_#_', '_S_', or '_E_'.\n\nThere will be exactly one '_S_' and exactly one '_E_' in the maze.\n\nThe 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."},{"iden":"output","content":"Print a single integer, the number of mappings of digits to directions that will lead the robot to the exit."},{"iden":"examples","content":"Input\n\n5 6\n.....#\nS....#\n.#....\n.#....\n...E..\n333300012\n\nOutput\n\n1\n\nInput\n\n6 6\n......\n......\n..SE..\n......\n......\n......\n01232123212302123021\n\nOutput\n\n14\n\nInput\n\n5 3\n...\n.S.\n###\n.E.\n...\n3\n\nOutput\n\n0"},{"iden":"note","content":"For the first sample, the only valid mapping is , where _D_ is down, _L_ is left, _U_ is up, _R_ is right."}],"translated_statement":[{"iden":"statement","content":"Bob 编程了一个机器人来导航一个二维迷宫。\n\n迷宫中有一些障碍物。空格用字符 '_._' 表示，障碍物用 '_#_' 表示。\n\n迷宫中有一个机器人，其起始位置用字符 '_S_' 表示。该位置没有障碍物。迷宫中也有一个出口，其位置用字符 '_E_' 表示。该位置也没有障碍物。\n\n机器人只能向上、左、右或下移动。\n\n当 Bob 编程机器人时，他写下了一个由数字 0 到 3 组成的字符串。他原本打算让每个数字对应一个不同的方向，机器人将按顺序执行这些指令以到达出口。但不幸的是，他忘记实际将方向分配给数字了。\n\n机器人将随机选择一个将数字映射到不同方向的方案。机器人会将不同的数字映射到不同的方向，然后按照给定字符串的顺序和所选映射执行指令。如果某条指令会导致机器人移出迷宫边界或撞上障碍物，机器人将崩溃并停止。如果机器人在任何时刻到达出口，则会停止执行后续指令。\n\nBob 正在调试他的机器人，因此他希望确定有多少种将数字映射到方向的方案能使机器人到达出口。\n\n输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[2 ≤ n, m ≤ 50]），表示迷宫的尺寸。\n\n接下来的 #cf_span[n] 行每行包含恰好 #cf_span[m] 个字符，表示迷宫。\n\n迷宫中的每个字符为 '_._'、'_#_'、'_S_' 或 '_E_'。\n\n迷宫中恰好有一个 '_S_' 和恰好一个 '_E_'。\n\n最后一行包含一个字符串 #cf_span[s]（#cf_span[1 ≤ |s| ≤ 100]）——提供给机器人的指令。#cf_span[s] 的每个字符都是 0 到 3 的数字。\n\n请输出一个整数，表示能使机器人到达出口的数字到方向的映射方案数。\n\n对于第一个样例，唯一有效的映射是：#cf_span[D] 表示向下，#cf_span[L] 表示向左，#cf_span[U] 表示向上，#cf_span[R] 表示向右。"},{"iden":"input","content":"输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[2 ≤ n, m ≤ 50]），表示迷宫的尺寸。接下来的 #cf_span[n] 行每行包含恰好 #cf_span[m] 个字符，表示迷宫。迷宫中的每个字符为 '_._'、'_#_'、'_S_' 或 '_E_'。迷宫中恰好有一个 '_S_' 和恰好一个 '_E_'。最后一行包含一个字符串 #cf_span[s]（#cf_span[1 ≤ |s| ≤ 100]）——提供给机器人的指令。#cf_span[s] 的每个字符都是 0 到 3 的数字。"},{"iden":"output","content":"请输出一个整数，表示能使机器人到达出口的数字到方向的映射方案数。"},{"iden":"examples","content":"输入\n5 6\n.....\n#S...\nn#.#.\n.....\n#....\nE..\n333300012\n输出\n1\n\n输入\n6 6\n................\nSE................\n................\n01232123212302123021\n输出\n14\n\n输入\n5 3\n...\n.S.\n###\n.E.\n...\n3\n输出\n0"},{"iden":"note","content":"对于第一个样例，唯一有效的映射是：#cf_span[D] 表示向下，#cf_span[L] 表示向左，#cf_span[U] 表示向上，#cf_span[R] 表示向右。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z} $ be the dimensions of the maze.  \nLet $ M \\in \\{\\text{.}, \\#, S, E\\}^{n \\times m} $ be the maze grid.  \nLet $ (s_r, s_c) \\in \\{1, \\dots, n\\} \\times \\{1, \\dots, m\\} $ be the unique start position where $ M[s_r][s_c] = S $.  \nLet $ (e_r, e_c) \\in \\{1, \\dots, n\\} \\times \\{1, \\dots, m\\} $ be the unique exit position where $ M[e_r][e_c] = E $.  \nLet $ s \\in \\{0,1,2,3\\}^* $ be the instruction string, with $ |s| = L $.  \n\nLet $ \\mathcal{D} = \\{ \\text{up}, \\text{down}, \\text{left}, \\text{right} \\} $ be the set of four cardinal directions.  \nLet $ \\Pi $ be the set of all bijections $ \\pi: \\{0,1,2,3\\} \\to \\mathcal{D} $; $ |\\Pi| = 4! = 24 $.  \n\nFor a mapping $ \\pi \\in \\Pi $, define the robot’s trajectory $ (x_0, y_0), (x_1, y_1), \\dots, (x_L, y_L) $ as:  \n- $ (x_0, y_0) = (s_r, s_c) $  \n- For $ i = 1 $ to $ L $:  \n  Let $ d = \\pi(s[i-1]) $  \n  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 $:  \n  - $ \\text{up}: (-1, 0) $, $ \\text{down}: (1, 0) $, $ \\text{left}: (0, -1) $, $ \\text{right}: (0, 1) $  \n  If $ (x_i, y_i) $ is out of bounds or $ M[x_i][y_i] = \\# $, the trajectory **crashes** at step $ i $.  \n  If $ (x_i, y_i) = (e_r, e_c) $, the trajectory **succeeds** and stops.  \n\n**Constraints**  \n1. $ 2 \\le n, m \\le 50 $  \n2. $ 1 \\le |s| \\le 100 $  \n3. Exactly one $ S $ and one $ E $ in $ M $  \n4. $ S, E \\neq \\# $  \n\n**Objective**  \nCount the number of mappings $ \\pi \\in \\Pi $ such that the robot’s trajectory under $ \\pi $:  \n- Does **not crash** at any step, and  \n- Reaches $ (e_r, e_c) $ at some step $ i \\le L $.","simple_statement":null,"has_page_source":false}