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.


-----Examples-----
Input
5 6
.....#
S....#
.#....
.#....
...E..
333300012

Output
1

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

Output
14

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

Output
0



-----Note-----

For the first sample, the only valid mapping is $0 \rightarrow D, 1 \rightarrow L, 2 \rightarrow U, 3 \rightarrow R$, where D is down, L is left, U is up, R is right.

Difficulty: interview

Starter code:

Solutions:
import itertools

def valid(grid, path, perm, start, goal):
    x, y = start
    n = len(grid)
    m = len(grid[0])
    for move in path:
        dx, dy = perm[int(move)]
        x += dx
        y += dy
        if (x, y) == goal:
            return True
        if not (0 <= x < n and 0 <= y < m) or grid[x][y] == '#':
            return False

    return False

def main():
    n, m = list(map(int, input().split()))
    grid = [list(input()) for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if grid[i][j] == 'S':
                sx, sy = i, j
                grid[i][j] = '.'
            elif grid[i][j] == 'E':
                gx, gy = i, j
                grid[i][j] = '.'


    path = input()
    moves = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    ans = 0
    for perm in itertools.permutations(moves):
        if valid(grid, path, perm, (sx, sy), (gx, gy)):
            ans += 1

    print(ans)

main()


from itertools import permutations

dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]

n, m = list(map(int, input().split()))
s = [input() for _ in range(n)]

spos = (0, 0)
for i in range(n):
    for j in range(m):
        if s[i][j] == 'S':
            spos = (j, i)

t = input()

ans = 0
for p in permutations(dirs):
    x, y = spos
    for c in t:
        dr = p[int(c)]
        x += dr[0]
        y += dr[1]
        if not 0 <= x < m or not 0 <= y < n:
            break
        if s[y][x] == '#':
            break
        if s[y][x] == 'E':
            ans += 1
            break

print(ans)


import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = [input() for i in range(n)]
s = input().strip()

for i in range(n):
  for j in range(m):
    if a[i][j] == 'S':
      sx, sy = i, j
    if a[i][j] == 'E':
      ex, ey = i, j

ans = 0

import itertools
for p in itertools.permutations([(-1, 0), (1, 0), (0, 1), (0, -1)], 4):
  x, y = sx, sy
  good = True
  for v in s:
    x += p[int(v)][0]
    y += p[int(v)][1]
    if not(0 <= x < n and 0 <= y < m and a[x][y] != '#'):
      good = False
    if (x, y) == (ex, ey):
      break
  if (x, y) != (ex, ey):
    good = False
  if good:
    ans += 1
  
print(ans)

from collections import defaultdict as di
n,m = [int(x) for x in input().split()]
free = di(lambda:False)
startpos = (-1,-1)
goal = (-1,-1)
for y in range(n):
    s = input()
    for x in range(m):
        c = s[x]
        if c=='S':
            startpos=(x,y)
            free[(x,y)]=True
        elif c=='E':
            goal=(x,y)
            free[(x,y)]=True
        elif c=='.':
            free[(x,y)]=True
counts = 0
dire = '0123'
command = input()
for up in dire:
    for down in dire:
        for right in dire:
            for left in dire:
                if len(set([up,down,left,right]))<4:
                    continue
                pos = startpos
                for c in command:
                    x,y = pos
                    if c == up:
                        y+=1
                    elif c == down:
                        y-=1
                    elif c==right:
                        x+=1
                    else:
                        x-=1
                    pos = (x,y)
                    if pos == goal:
                        counts += 1
                        break
                    if not free[pos]:
                        break

print(counts)


n, m = map(int, input().split())
a = []
startx = 0
starty = 0
for i in range(n):
    a.append(input())
    if ("S" in a[i]):
        startx = a[i].index('S')
        starty = i
        
s = input()
ans = 0
for l in range(4):
    for r in range(4):
        if r == l: continue
        for u in range(4):
            if u == r or u == l: continue
            for d in range(4):
                if (d == u or d == r or d == l): continue
                posx = startx
                posy = starty
                for i in s:
                    i = int(i)
                    if (i == l):
                        posx -= 1
                    elif (i == r):
                        posx += 1
                    elif (i == d):
                        posy += 1
                    elif (i == u):
                        posy -= 1
                    
                    if (posy < 0 or posy >= n or posx < 0 or posx >= m):
                        break
                    elif (a[posy][posx] == '#'):
                        break
                    elif (a[posy][posx] == 'E'):
                        ans += 1
                        break
                    
print(ans)

import itertools as I

h,w = list(map(int,input().split()))
M = [list(input()) for _ in range(h)]
cmds = input()

def ok(x,y):
    return 0 <= x < w and 0 <= y < h and M[y][x]!='#'

start = None
end = None
for i in range(h):
    for j in range(w):
        if M[i][j] == 'S':
            start = (j,i)
        if M[i][j] == 'E':
            end = (j,i)
         
cnt = 0
for dirs in I.permutations([(1,0),(0,1),(-1,0),(0,-1)]):
    x,y = start
    for c in cmds:
        dx,dy = dirs[int(c)]
        x += dx
        y += dy
        if not ok(x,y):
            break
        if M[y][x] == 'E':
            cnt += 1
            break
print(cnt)


from itertools import permutations
n, m = list(map(int, input().split()))
M = [input() for i in range(n)]
for i in range(n):
    for j in range(m):
        if M[i][j] == 'S':
            sx = j; sy = i
        elif M[i][j] == 'E':
            ex = j; ey = i
*S, = list(map(int, input()))

dd = [[-1, 0], [0, -1], [1, 0], [0, 1]]

def solve(p):
    x = sx; y = sy
    for c in S:
        dx, dy = dd[p[c]]
        x += dx; y += dy
        if (not 0 <= x < m) or (not 0 <= y < n) or (M[y][x] == '#'):
            return 0
        if x == ex and y == ey:
            return 1
    return 0

ans = 0
for p in permutations(list(range(4))):
    ans += solve(p)
print(ans)


r, s = list(map(int, input().split()))
m = []
for i in range(r):
    m.append(input())
    for j in range(s):
        if m[i][j] == 'S':
            start = i, j
se = input()
u = [0, 1, 0, -1]
v = [1, 0, -1, 0]
sol = 0
for a in range(4):
    for b in range(4):
        for c in range(4):
            for d in range(4):
                if len(set([a, b, c, d])) < 4:
                    continue
                x, y = start
                cnt = 0
                for znak in se:
                    if znak == '0':
                        x += u[a]
                        y += v[a]
                    if znak == '1':
                        x += u[b]
                        y += v[b]
                    if znak == '2':
                        x += u[c]
                        y += v[c]
                    if znak == '3':
                        x += u[d]
                        y += v[d]
                    cnt += 1
                    if x < 0 or y < 0 or x >= r or y >= s:
                        cnt = -1
                        break
                    if m[x][y] not in ['.', 'S']:
                        break
                #print(a, b, c, d, m[x][y], cnt, x, y)
                if cnt > 0 and m[x][y] == 'E':
                    sol += 1
print(sol)


import itertools

n, m = [int(v) for v in input().split()]
l = [input() for _ in range(n)]
dirs = [int(c) for c in input()]

start, end = None, None
for i, line in enumerate(l):
    ps = line.find('S')
    pe = line.find('E')
    if ps != -1:
        start = (ps, i)
    if pe != -1:
        end = (pe, i)

# up, down, left, right
ways = [(0, -1), (0, 1), (-1, 0), (1, 0)]
cnt = 0

for p in itertools.permutations(list(range(4))):
    dst = [ways[pp] for pp in p]
    px, py = start
    for d in dirs:
        px += dst[d][0]
        py += dst[d][1]
        if px < 0 or px >= m or py < 0 or py >= n or l[py][px] == '#':
            break
        if (px, py) == end:
            cnt += 1
            break

print(cnt)


import sys

dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]
rows, cols = map(int, sys.stdin.readline().split())

b = ['' for row in range(rows)]
sr, sc = 0, 0
er, ec = 0, 0
for row in range (rows):
  b[row] = sys.stdin.readline().strip()
  if 'S' in b[row]:
    sr, sc = row, b[row].index('S')
  if 'E' in b[row]:
    er, ec = row, b[row].index('E')


dirs = sys.stdin.readline().strip()

res = 0
for i in range (4):
  for j in range (4):
    for k in range (4):
      if j != i and i != k and j != k:
        l = (0+1+2+3) - (i+j+k)
        r, c = sr, sc
        p = [i, j, k, l]
        ok = 0
        for d in dirs:
          di = int(d)
          r += dr[p[di]]
          c += dc[p[di]]
          if r < 0 or r >= rows or c < 0 or c >= cols or b[r][c] == '#':
            break
          if b[r][c] == 'E':
            ok = 1
        res += ok

print (res)         

n,m = list(map(int,input().split()))
grid = []
sloc = (-1,-1)
eloc = (-1,-1)
for y in range(n):
    l = input()
    grid.append(list())
    for x in range(m):
        grid[-1].append(l[x]=='#')
        if l[x]=='S':
            sloc = (x,y)
        elif l[x]=='E':
            eloc = (x,y)

pb = []
for a in [(0,1),(0,-1),(1,0),(-1,0)]:
    for b in [(0,1),(0,-1),(1,0),(-1,0)]:
        for c in [(0,1),(0,-1),(1,0),(-1,0)]:
            for d in [(0,1),(0,-1),(1,0),(-1,0)]:
                if len(set([a,b,c,d]))==4 and [a,b,c,d] not in pb:
                    pb.append([a,b,c,d])

s = input()

ans = 0
for mp in pb:
    seen = False
    works = True
    loc = sloc
    for j in s:
        j = int(j)
        if seen:
            break
        if not works:
            break
        nloc = (loc[0]+mp[j][0],loc[1]+mp[j][1])
        if min(nloc)<0 or nloc[0]>=m or nloc[1]>=n:
            works = False
            break
        if grid[nloc[1]][nloc[0]]:
            works = False
            break
        if nloc == eloc:
            seen = True
            break
        loc = nloc
    if seen:
        ans+=1

print(ans)


import sys

#f = open('input', 'r')
f = sys.stdin
ms = tuple(map(int, f.readline().split()))
d = [(0, 1), (0, -1), (1, 0), (-1, 0)]
mp = []
for i in range(ms[0]):
  mp.append(f.readline().strip())
  for j in range(ms[1]):
    if mp[i][j] == 'S':
      start_pos = (i, j)
    elif mp[i][j] == 'E':
      end_pos = (i, j)

go = f.readline().strip()
import itertools
ans = 0
for dp in itertools.permutations(d):
  cur_pos = start_pos
  failed = False
  for x in go:
    cur_pos = tuple(map(sum, list(zip(cur_pos, dp[int(x)]))))
    for p, q in zip(cur_pos, ms):
      if p < 0 or p >= q:
        failed = True
    if failed:
      break
    if mp[cur_pos[0]][cur_pos[1]] == '#':
      failed = True
      break
    elif mp[cur_pos[0]][cur_pos[1]] == 'E':
      failed = False
      break
  if not failed and mp[cur_pos[0]][cur_pos[1]] == 'E':
    ans += 1
print(ans)


import itertools

r, c = input().split()
r, c = int(r), int(c)

def add(a, b):
    return (a[0] + b[0], a[1] + b[1])

def is_valid(k, r, c):
    return (0 <= k[0] < r) and (0 <= k[1] < c)

m = [input() for x in range(r)]

for a in range(r):
    for b in range(c):
        if m[a][b] == 'S':
            start = (a, b)
        elif m[a][b] == 'E':
            end = (a, b)

d = input()
t = 0

for p in itertools.permutations([(0, 1), (0, -1), (-1, 0), (1, 0)]):
    poss = True
    curr = start
    
    for i in d:
        curr = add(curr, p[int(i)])
        
        if (curr == end):
            break

        if (is_valid(curr, r, c)) and (m[curr[0]][curr[1]] != '#'):
            continue
        
        poss = False
        break
    
    if poss and (curr == end):
        t += 1

print(t)


n, m = list(map(int, input().split()))
d = []
for i in range(n):
	d.append(input())
	if 'S' in d[-1]:
		s = [i, d[-1].index('S')]
	if 'E' in d[-1]:
		e = [i, d[-1].index('E')]
p = input()
dic = {'n': [-1, 0], 'e':[0,1], 's':[1, 0], 'w':[0,-1]}
import itertools as it
z = it.permutations('news', 4)
res = 0
for i in z:
	st = s
	et = e
	q = {'0123'[j]:dic[i[j]] for j in range(4)}
	for j in p:
		cur = q[j]
		st = [st[0] + cur[0], st[1] + cur[1]]
		if st[0] < 0 or st[0] >= n or st[1] < 0 or st[1] >= m or d[st[0]][st[1]] == '#':
			break
		if st == et:
			break
	if st == et:
		res += 1
print(res)


def onGrid(p):
  if p.real >= 0 and p.real < n and p.imag >= 0 and p.imag < m:
    return True
from itertools import permutations
n,m = map(int, input().split())
grid = [input() for a in range(n)]
for a in range(n):
  if "S" in grid[a]:
    start = a+1j*grid[a].index("S")
  if "E" in grid[a]:
    end = a+1j*grid[a].index("E")
ways = list(permutations([1,-1,1j,-1j],4))
count = 0
instructions = input()
for way in ways:
  coords = start+0
  for i in instructions:
    coords += way[int(i)]
    if not onGrid(coords) or grid[int(coords.real)][int(coords.imag)] == "#":
      break
    if coords == end:
      count += 1
      break
print(count)

n, m = map(int, input().split())
grid = []
for i in range(n):
	grid.append(input())
	if grid[-1].find('S') > -1:
		S = (i, grid[-1].find('S'))
	if grid[-1].find('E') > -1:
		E = (i, grid[-1].find('E'))

string = input()

directions = []
def all_permutations(seq):
	if len(seq) == 0:
		yield []
	for i in seq:
		for p in all_permutations([x for x in seq if x!=i]):
			yield [i] + p

d_map = [(0,-1), (1,0), (0,1), (-1,0)]
ans = 0
for p in all_permutations([0,1,2,3]):
	#0 goes in direction d_map[p[0]]
	cr = S[0]
	cc = S[1]
	for i in string:
		cr = cr + d_map[p[int(i)]][0]
		cc = cc + d_map[p[int(i)]][1]
		if cr >= n or cr < 0 or cc >= m or cc < 0 or grid[cr][cc] == "#":
			break
		if grid[cr][cc] == "E":
			ans += 1
			break
		

print(ans)

import itertools

dirs = (list(itertools.permutations(['r', 'l', 'd', 'u'])))

n,m = list(map(int, input().split()))
grid = []
for i in range(n):
	grid.append(input())

path = input()

dx = {
	'r': 0,
	'l': 0,
	'u': -1,
	'd': 1
}
dy = {
	'r': 1,
	'l': -1,
	'u': 0,
	'd': 0
}

def can_reach(n, m, grid, adir, path, dx, dy):
	x = y = 0
	for i in range(n):
		for j in range(m):
			if grid[i][j] == 'S':
				x = i
				y = j
	for i in range(len(path)):
		x += dx[adir[int(path[i])]]
		y += dy[adir[int(path[i])]]
		if x >= n or y >= m or x < 0 or y < 0 or grid[x][y] == '#':
			return False
		if grid[x][y] == 'E':
			return True
				

cnt = 0
for adir in dirs:
	if can_reach(n, m, grid, adir, path, dx, dy):
		cnt+=1
print(cnt)



import itertools

n, m = list(map(int, input().split()))
maze = [input() for i in range(n)]
for i in range(n):
    for j in range(m):
        if maze[i][j] == 'S':
            sy = i
            sx = j
        elif maze[i][j] == 'E':
            ey = i
            ex = j
s = [int(c) for c in input()]
cnt = 0
for p in itertools.permutations([(0, 1), (0, -1), (1, 0), (-1, 0)], r=4):
    y = sy
    x = sx
    for i in s:
        dy, dx = p[i]
        if 0 <= y + dy < n and 0 <= x + dx < m and maze[y+dy][x+dx] != '#':
            y += dy
            x += dx
        else:
            break
        if y == ey and x == ex:
            break
    if y == ey and x == ex:

        cnt += 1
print(cnt)


n, m = map(int, input().split())
a = []
start = None
for i in range(n):
    s = input()
    a.append(s)
    if 'S' in s:
        start = [i, s.index('S')]
h = input()
ans = 0
ms = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def check(d):
    ps = [i for i in start]
    for l in h:
        nm = ms[d[int(l)]]
        dx, dy = nm
        ps = [ps[0] + dx, ps[1] + dy]
        if ps[0] >= n or ps[0] < 0 or ps[1] < 0 or ps[1] >= m or a[ps[0]][ps[1]] == '#':
            return False
        if a[ps[0]][ps[1]] == 'E':
            return True
    return False

for i in range(4):
    for j in range(4):
        if j != i:
            for k in range(4):
                if k not in [i, j]:
                    for z in range(4):
                        if z not in [i, j, k]:
                            if check({0: i, 1: j, 2: k, 3: z}):
                                ans += 1
print(ans)

# coding: utf-8

import itertools

def check(dirs, inst, maze, s):
    posy, posx = s
    rx = len(maze[0])
    ry = len(maze)
    for i in inst:
        if dirs[i] == "N":
            posy -= 1
        elif dirs[i] == "S":
            posy += 1
        elif dirs[i] == "E":
            posx += 1
        elif dirs[i] == "W":
            posx -= 1
        if posx < 0 or posx >= rx or posy < 0 or posy >= ry:
            return False
        if maze[posy][posx] == "#":
            return False
        if maze[posy][posx] == "E":
            return True
    return False


n, m = list(map(int, input().split()))
maze = []
for i in range(n):
    l = input().strip()
    maze.append(l)
    if "S" in l:
        s = (i, l.index("S"))
inst = list(map(int, input().strip()))
t = 0
for i in itertools.permutations("NWSE"):
    c = check(i, inst, maze, s)
    t += check(i, inst, maze, s)
print(t)


from itertools import permutations

def ok(n, m, v, a, l):
    x, y = -1, -1
    for i, q in enumerate(v):
        if 'S' in q:
            x = i
            y = q.index('S')
            break
    for i in l:
        if a[i] == 'u':
            x -= 1
        elif a[i] == 'd':
            x += 1
        elif a[i] == 'l':
            y += 1
        elif a[i] == 'r':
            y -= 1

        if x < 0 or x >= n or y < 0 or y >= m or v[x][y] == '#':
            return False

        if v[x][y] == 'E':
            return True
    
    if x < 0 or x >= n or y < 0 or y >= m or v[x][y] == '#':
        return False

    return v[x][y] == 'E'

n, m = map(int, input().split())

v = [input() for _ in range(n)]

l = list(map(int, input()))

ans = 0

for i in permutations(['u', 'd', 'l', 'r']):
    if ok(n, m, v, i, l):
        ans += 1

print(ans)


n,m=map(int,input().split())
def road(ins):
    cur=S.copy()
    for x in s:
        x=int(x)
        if ar[cur[0]][cur[1]]== 'E':
            return 1
        if ins[x]=='U':
            try:
                if ar[cur[0]+1][cur[1]] != '#':
                    cur=[cur[0]+1,cur[1]]
                else:
                    return 0
            except:
                return 0
        if ins[x]=='D':
            try:
                if ar[cur[0]-1][cur[1]] != '#' and cur[0]-1 >= 0:
                    cur=[cur[0]-1,cur[1]]
                else:
                    return 0
            except:
                return 0
        if ins[x]=='R':
            try:
                if ar[cur[0]][cur[1]+1] != '#':
                    cur=[cur[0],cur[1]+1] 
                else:
                    return 0
            except:
                return 0
        if ins[x]=='L':
            try:
                if ar[cur[0]][cur[1]-1] != '#' and cur[1]-1 >= 0:
                    cur=[cur[0],cur[1]-1] 
                else:
                    return 0
            except:
                return 0
    #print(cur)
    if ar[cur[0]][cur[1]]== 'E':
        return 1
    else:
        return 0
ar=[input() for x in range(n)]
S=[0,0]
E=[0,0]
for x in range(n):
    if 'S' in ar[x]:
        S=[x,ar[x].index('S')]
    if 'E' in ar[x]:
        E=[x,ar[x].index('E')]
s=input()
import itertools
i=0
for x in list(itertools.permutations(['U','D','L','R'])):
    #print(list(x))
    i+= road(list(x))
print(i)