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.

Source: codeforces | Difficulty: EASY
Tags: Implementation

Complete search


Solutions:
from itertools import permutations
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
per = permutations(dirs)
(r, c) = map(int, input().split())
grid = [input() for _ in range(r)]
path = input()
pos_start = [i for (i, x) in enumerate(grid) if 'S' in x][0]
start = (pos_start, grid[pos_start].index('S'))
pos_end = [i for (i, x) in enumerate(grid) if 'E' in x][0]
end = (pos_end, grid[pos_end].index('E'))
total = 0
for p in per:
	(x, y) = start
	for move in path:
		(dir_x, dir_y) = p[int(move)]
		x += dir_x
		y += dir_y
		if x < 0 or y < 0 or x >= r or (y >= c) or (grid[x][y] == '#'):
			break
		if grid[x][y] == 'E':
			total += 1
			break
print(total)


(n, m) = 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)


import itertools
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
(n, m) = map(int, input().split())
s = [input() for i in range(n)]
a = input()
for i in range(n):
	for j in range(m):
		if s[i][j] == 'S':
			sx = i
			sy = j

def inside(x, y):
	return x >= 0 and x < n and (y >= 0) and (y < m)

def check(p):
	x = sx
	y = sy
	for i in a:
		id = p[int(i)]
		x += d[id][0]
		y += d[id][1]
		if not inside(x, y) or s[x][y] == '#':
			return 0
		if s[x][y] == 'E':
			return 1
	return 0
print(sum((check(i) for i in itertools.permutations([0, 1, 2, 3]))))


(a, b) = map(int, input().split())
x = []
y = []
z = []
for i in range(a):
	c = str(input())
	x.append(c)
	if 'S' in c:
		y.append(i)
		y.append(c.index('S'))
	if 'E' in c:
		z.append(i)
		z.append(c.index('E'))
d = str(input())
e = ['0123', '0132', '0213', '0231', '0312', '0321', '1023', '1032', '1203', '1230', '1302', '1320', '2013', '2031', '2103', '2130', '2301', '2310', '3012', '3021', '3102', '3120', '3201', '3210']
sum = 0
for i in range(len(e)):
	j = y[0]
	k = y[1]
	l = 0
	while (j != z[0] or k != z[1]) and l < len(d):
		if d[l] == e[i][0]:
			j += 1
		elif d[l] == e[i][1]:
			k -= 1
		elif d[l] == e[i][2]:
			j -= 1
		elif d[l] == e[i][3]:
			k += 1
		if j < a and k < b and (j >= 0) and (k >= 0):
			if x[j][k] == 'E':
				sum += 1
				break
			elif x[j][k] == '.':
				pass
			elif x[j][k] == '#':
				break
		else:
			break
		l += 1
print(sum)


def dfs(ii, jj, nnum):
	global num, s, ans, d_map
	for v in d_map:
		if num.index(v) == 0:
			ii += 1
		elif num.index(v) == 1:
			jj -= 1
		elif num.index(v) == 2:
			ii -= 1
		else:
			jj += 1
		if ii < 0 or jj < 0 or ii == n or (jj == m):
			return
		if s[ii][jj] == '#':
			return
		if s[ii][jj] == 'E':
			ans += 1
			return
(n, m) = map(int, input().split())
s = []
for i in range(n):
	s.append(list(input()))
d_map = list(map(int, list(input())))
nnum = len(d_map)
(s_i, s_j) = (0, 0)
for i in range(n):
	for j in range(m):
		if s[i][j] == 'S':
			(s_i, s_j) = (i, j)
ans = 0
for x1 in range(4):
	for x2 in range(4):
		for x3 in range(4):
			for x4 in range(4):
				num = [x1, x2, x3, x4]
				if sorted(num) == [0, 1, 2, 3]:
					dfs(s_i, s_j, nnum)
print(ans)


def do_step(x: int, y: int, type: int):
	if type == 0:
		return (x, y + 1)
	elif type == 1:
		return (x + 1, y)
	elif type == 2:
		return (x, y - 1)
	else:
		return (x - 1, y)
(n, m) = map(int, input().split())
gr = []
(sx, sy) = (0, 0)
(ex, ey) = (0, 0)
for i in range(n):
	gr.append(list(input()))
	for j in range(m):
		if gr[i][j] == 'S':
			sx = (i,)
			sy = (j,)
		if gr[i][j] == 'E':
			ex = i
			ey = j
s = list(map(int, list(input())))
ans = 0
for zero in range(4):
	for one in range(4):
		if one != zero:
			for two in range(4):
				if one != two and two != zero:
					for three in range(4):
						if three != one and three != zero and (three != two):
							steps = [zero, one, two, three]
							(x, y) = (sy[0], sx[0])
							for i in s:
								(x, y) = do_step(x, y, steps[i])
								if x == m or x == -1 or y == n or (y == -1) or (gr[y][x] == '#'):
									break
								if x == ey and y == ex:
									ans += 1
									break
print(ans)


(r, s) = 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
				if cnt > 0 and m[x][y] == 'E':
					sol += 1
print(sol)


from itertools import permutations

def main():
	(n, m) = map(int, input().split())
	g = [input() for _ in range(n)]
	s = [(i, j) for i in range(n) for j in range(m) if g[i][j] == 'S'][0]
	p = tuple(map(int, input()))
	ans = 0
	for var in permutations(((-1, 0), (0, -1), (0, 1), (1, 0))):
		(i, j) = s
		for c in p:
			(i, j) = (i + var[c][0], j + var[c][1])
			if i < 0 or i >= n or j < 0 or (j >= m) or (g[i][j] == '#'):
				break
			if g[i][j] == 'E':
				ans += 1
				break
	print(ans)
main()


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)


from sys import stdin
import itertools

def make_move(mapping, instruction, curr_coord):
	move = mapping[instruction]
	(y, x) = curr_coord
	if move == 'U':
		return (y - 1, x)
	elif move == 'D':
		return (y + 1, x)
	elif move == 'R':
		return (y, x + 1)
	elif move == 'L':
		return (y, x - 1)
(n, m) = map(int, stdin.readline().split())
terrain = []
obstacles = []
for i in range(n):
	line = stdin.readline().strip()
	if 'S' in line:
		start_coord = (i, line.index('S'))
	if 'E' in line:
		end_coord = (i, line.index('E'))
	obstacles += [(i, ind) for ind in range(len(line)) if line[ind] == '#']
	terrain.append(line)
instructions = stdin.readline().strip()
perms = list(itertools.permutations(['0', '1', '2', '3']))
found = 0
for perm in perms:
	curr_coord = start_coord
	mapping = {perm[0]: 'U', perm[1]: 'R', perm[2]: 'D', perm[3]: 'L'}
	for i in range(len(instructions)):
		curr_coord = make_move(mapping, instructions[i], curr_coord)
		if curr_coord in obstacles or curr_coord[1] >= m or curr_coord[1] < 0 or (curr_coord[0] < 0) or (curr_coord[0] >= n):
			break
		if curr_coord == end_coord:
			found += 1
			break
print(found)


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)


def permute(l):
	length = len(l)
	if length <= 1:
		yield l
	else:
		for n in range(length):
			for end in permute(l[:n] + l[n + 1:]):
				yield ([l[n]] + end)

def is_ok(mapping, directions, x, y):
	for direction in directions:
		if mapping[direction][0] + x < 0 or mapping[direction][0] + x >= n or mapping[direction][1] + y >= m or (mapping[direction][1] + y < 0) or (maze[mapping[direction][0] + x][mapping[direction][1] + y] == '#'):
			return 0
		if maze[mapping[direction][0] + x][mapping[direction][1] + y] == 'E':
			return 1
		x += mapping[direction][0]
		y += mapping[direction][1]
	return 0
(n, m) = tuple((int(t) for t in input().rstrip().split(' ')))
maze = list()
for _ in range(n):
	maze.append(list(input().rstrip()))
directions = list(input().rstrip())
possible_directions = [[1, 0], [0, 1], [0, -1], [-1, 0]]
for i in range(n):
	for j in range(m):
		if maze[i][j] == 'S':
			x = i
			y = j
			break
counter = 0
for p in permute(['0', '1', '2', '3']):
	mapping = dict()
	for i in range(4):
		mapping[p[i]] = possible_directions[i]
	counter += is_ok(mapping, directions, x, y)
print(counter)


import itertools
(n, m) = [int(x) for x in input().split()]
A = [input() for x in range(0, n)]
s = input()
Sx = 0
Sy = 0
for x in range(0, n):
	if 'S' in A[x]:
		Sy = x
for x in range(0, m):
	if 'S' in [row[x] for row in A]:
		Sx = x

def test(p):
	x = Sx
	y = Sy
	for j in s:
		d = p[int(j)]
		if d == 0:
			x -= 1
		if d == 1:
			y -= 1
		if d == 2:
			x += 1
		if d == 3:
			y += 1
		if x >= m or x < 0 or y >= n or (y < 0):
			return 0
		if A[y][x] == '#':
			return 0
		if A[y][x] == 'E':
			return 1
	return 0
ans = 0
for p in itertools.permutations([0, 1, 2, 3]):
	ans += test(p)
print(ans)


import itertools
(n, m) = map(int, input().split())
g = [None for j in range(n)]
posst = 0
posen = 0
for i in range(n):
	g[i] = input()
	if posst != 0 and posen != 0:
		continue
	for j in range(m):
		if g[i][j] == 'S':
			posst = (i, j)
		elif g[i][j] == 'E':
			posen = (i, j)
s = input()
L = list(itertools.permutations(['L', 'R', 'D', 'U']))
g1 = [None for i in range(len(L))]
for i in range(len(L)):
	g1[i] = {'0': L[i][0], '1': L[i][1], '2': L[i][2], '3': L[i][3]}

def solve(s, dic):
	global posst, m, n
	for x in s:
		d = dic[x]
		if d == 'L' and posst[1] > 0:
			if g[posst[0]][posst[1] - 1] != '#':
				posst = (posst[0], posst[1] - 1)
			else:
				return 0
		elif d == 'R' and posst[1] < m - 1:
			if g[posst[0]][posst[1] + 1] != '#':
				posst = (posst[0], posst[1] + 1)
			else:
				return 0
		elif d == 'U' and posst[0] > 0:
			if g[posst[0] - 1][posst[1]] != '#':
				posst = (posst[0] - 1, posst[1])
			else:
				return 0
		elif d == 'D' and posst[0] < n - 1:
			if g[posst[0] + 1][posst[1]] != '#':
				posst = (posst[0] + 1, posst[1])
			else:
				return 0
		else:
			return 0
		if posst == posen:
			return 1
	return 0
ans = 0
pp = posst
for i in range(len(g1)):
	dic = g1[i]
	r = solve(s, dic)
	ans += r
	posst = pp
print(ans)


def check(p):
	global c
	(x, y) = (Sx, Sy)
	for i in s:
		n = p[int(i)]
		if n == 'U':
			y -= 1
		elif n == 'D':
			y += 1
		elif n == 'L':
			x -= 1
		elif n == 'R':
			x += 1
		if x == w or y == h or x < 0 or (y < 0):
			return
		elif L[y][x] == '#':
			return
		elif L[y][x] == 'E':
			c += 1
			return
(h, w) = map(int, input().split())
L = []
for i in range(h):
	L.append(list(input()))
	if 'S' in L[-1]:
		(Sy, Sx) = (i, L[-1].index('S'))
s = input()
sl = len(s)
c = 0
a = {'U', 'D', 'R', 'L'}
for a1 in a:
	_a1 = a.copy()
	_a1.discard(a1)
	for a2 in _a1:
		_a2 = _a1.copy()
		_a2.discard(a2)
		for a3 in _a2:
			_a3 = _a2.copy()
			_a3.discard(a3)
			check([a1, a2, a3, _a3.pop()])
print(c)


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 itertools import permutations
(y, x) = map(int, input().split())
M = ['' for i in range(y)]
for i in range(y):
	M[i] = input()
path = input()
for i in range(y):
	for j in range(x):
		if M[i][j] == 'S':
			starty = i
			startx = j
mappings = permutations('0123')
direction_x = [0, 1, 0, -1]
direction_y = [1, 0, -1, 0]
ans = 0
for mapping in mappings:
	mappath = [mapping[int(c)] for c in path]
	posy = starty
	posx = startx
	for direction in mappath:
		direction = int(direction)
		posy += direction_y[direction]
		posx += direction_x[direction]
		if not (posy >= 0 and posy < y):
			break
		if not (posx >= 0 and posx < x):
			break
		if M[posy][posx] == '#':
			break
		if M[posy][posx] == 'E':
			ans += 1
			break
print(ans)


def check(x, y):
	global n, m, Mass
	if x >= 0 and x < n and (y >= 0) and (y < m):
		if Mass[x][y] == 'E':
			return 2
		if Mass[x][y] != '#':
			return 1
		return -1
	return -1
(n, m) = map(int, input().split())
Mass = []
(X, Y) = (-1, -1)
for i in range(n):
	Dik = input()
	Mass.append(Dik)
	if X == -1:
		for j in range(len(Dik)):
			if Dik[j] == 'S':
				(X, Y) = (i, j)
S = input()
k = 0
for i1 in range(4):
	for i2 in range(4):
		for i3 in range(4):
			for i4 in range(4):
				Set = set()
				Set.add(i1)
				Set.add(i2)
				Set.add(i3)
				Set.add(i4)
				if len(Set) == 4:
					(D, L, U, R) = (i1, i2, i3, i4)
					(x, y) = (X, Y)
					Flag = True
					for i in S:
						if int(i) == D:
							x -= 1
						if int(i) == L:
							y -= 1
						if int(i) == U:
							x += 1
						if int(i) == R:
							y += 1
						if check(x, y) == -1:
							Flag = False
							break
						elif check(x, y) == 2:
							break
					if Flag and check(x, y) == 2:
						k += 1
print(k)


from itertools import permutations as p
(n, m) = map(int, input().split())
data = [input() for _ in range(n)]
route = input()
for i in range(n):
	for j in range(m):
		if data[i][j] == 'S':
			s = [i, j]
		elif data[i][j] == 'E':
			e = [i, j]
ans = 0
for (d, l, u, r) in list(p('0123')):
	c = s[:]
	for x in route:
		if x == u:
			c[0] -= 1
			if c == e:
				ans += 1
				break
			if c[0] < 0 or data[c[0]][c[1]] == '#':
				break
		elif x == d:
			c[0] += 1
			if c == e:
				ans += 1
				break
			if c[0] >= n or data[c[0]][c[1]] == '#':
				break
		elif x == l:
			c[1] -= 1
			if c == e:
				ans += 1
				break
			if c[1] < 0 or data[c[0]][c[1]] == '#':
				break
		elif x == r:
			c[1] += 1
			if c == e:
				ans += 1
				break
			if c[1] >= m or data[c[0]][c[1]] == '#':
				break
print(ans)


read = lambda : map(int, input().split())
(n, m) = read()
a = [input() for i in range(n)]
xs = ys = -1
s = list(map(int, input()))
for i in range(n):
	if a[i].find('S') != -1:
		xs = i
		ys = a[i].find('S')
cnt = 0
d = [(0, 1), (0, -1), (1, 0), (-1, 0)]
from itertools import permutations
for p in permutations(d):
	x = xs
	y = ys
	flag = 0
	for i in s:
		if a[x][y] == 'E':
			flag = 1
			break
		(dx, dy) = p[i]
		x += dx
		y += dy
		if x < 0 or x >= n or y < 0 or (y >= m):
			break
		if a[x][y] == '#':
			break
		if a[x][y] == 'E':
			flag = 1
			break
	if flag:
		cnt += 1
print(cnt)


flag = [True] * 4
D = []
x = [0] * 4
spos = 0
tmp = input()
(n, m) = tmp.split(' ')
n = int(n)
m = int(m)
matrix = [['0'] * m] * n
for i in range(n):
	matrix[i] = input()
	if 'S' in matrix[i]:
		spos = [i, matrix[i].index('S')]
s = input()

def generate(pos):
	if pos == 4:
		return
	for i in range(0, 4):
		if flag[i] == True:
			x[pos] = i
			if pos == 3:
				D.append(x.copy())
			flag[i] = False
			generate(pos + 1)
			flag[i] = True
generate(0)
c = 0
org_pos = spos.copy()
for d in D:
	spos = org_pos.copy()
	for t in s:
		i = int(t)
		if d[i] == 0:
			spos[0] += 1
		elif d[i] == 1:
			spos[0] -= 1
		elif d[i] == 2:
			spos[1] -= 1
		else:
			spos[1] += 1
		if spos[0] < 0 or spos[0] >= n or spos[1] < 0 or (spos[1] >= m) or (matrix[spos[0]][spos[1]] == '#'):
			break
		if matrix[spos[0]][spos[1]] == 'E':
			c += 1
			break
print(c)


(n, m) = map(int, input().split())
y = [(0, 1, 2, 3), (0, 1, 3, 2), (0, 2, 1, 3), (0, 2, 3, 1), (0, 3, 1, 2), (0, 3, 2, 1), (1, 0, 2, 3), (1, 0, 3, 2), (1, 2, 0, 3), (1, 2, 3, 0), (1, 3, 0, 2), (1, 3, 2, 0), (2, 0, 1, 3), (2, 0, 3, 1), (2, 1, 0, 3), (2, 1, 3, 0), (2, 3, 0, 1), (2, 3, 1, 0), (3, 0, 1, 2), (3, 0, 2, 1), (3, 1, 0, 2), (3, 1, 2, 0), (3, 2, 0, 1), (3, 2, 1, 0)]
a = []
for i in range(n):
	a.append(input())
for i in range(n):
	for j in range(m):
		if a[i][j] == 'S':
			sx = j
			sy = i
		if a[i][j] == 'E':
			fx = j
			fy = i
c = list(map(int, input()))
ans = 0
for b in y:
	x = sx + 0
	y = sy + 0
	for i in c:
		if i == b[0]:
			x -= 1
		elif i == b[1]:
			y -= 1
		elif i == b[2]:
			x += 1
		else:
			y += 1
		if x == fx and y == fy:
			ans += 1
			break
		if x < 0 or x >= m or y < 0 or (y >= n) or (a[y][x] == '#'):
			break
print(ans)


def make_move(cur_pos, dic, inst):
	inst = dic[inst]
	new_pos = (cur_pos[0] + inst[0], cur_pos[1] + inst[1])
	return new_pos
(N, M) = [int(i) for i in input().strip().split()]
grid = []
for n in range(N):
	grid.append(input().strip())
	if 'S' in grid[-1]:
		s_pos = (n, grid[-1].find('S'))
	if 'E' in grid[-1]:
		e_pos = (n, grid[-1].find('E'))
dirs = input().strip()
ans = 0
for l in range(4):
	for r in range(4):
		for u in range(4):
			for d in range(4):
				s = set()
				s.add(l)
				s.add(r)
				s.add(u)
				s.add(d)
				if len(s) != 4:
					continue
				dic = dict()
				dic[l] = (-1, 0)
				dic[r] = (1, 0)
				dic[u] = (0, 1)
				dic[d] = (0, -1)
				cur_pos = s_pos
				(good, bad) = (False, False)
				for inst in dirs:
					cur_pos = make_move(cur_pos, dic, int(inst))
					if cur_pos[0] >= N or cur_pos[0] < 0 or cur_pos[1] >= M or (cur_pos[1] < 0) or (grid[cur_pos[0]][cur_pos[1]] == '#'):
						bad = True
						break
					if grid[cur_pos[0]][cur_pos[1]] == 'E':
						good = True
						break
				if bad:
					continue
				if good:
					ans += 1
					continue
print(ans)


(r, c) = map(int, input().strip().split())
import itertools
code = list(itertools.permutations([0, 1, 2, 3]))
direc = [(0, 1), (0, -1), (1, 0), (-1, 0)]
board = []
for i in range(r):
	board.append([s for s in input().strip()])
step = list(map(int, [s for s in input().strip()]))
cnt = 0
(x, y) = (0, 0)
for i in range(r):
	for j in range(c):
		if board[i][j] == 'S':
			(xs, ys) = (i, j)
cnt = 0
for mapcode in code:
	(x, y) = (xs, ys)
	for j in step:
		x = x + direc[mapcode[j]][0]
		y = y + direc[mapcode[j]][1]
		if x < 0 or x >= r or y < 0 or (y >= c) or (board[x][y] == '#'):
			break
		if board[x][y] == 'E':
			cnt += 1
			break
print(cnt)


from itertools import permutations
(n, m) = map(int, input().split())
g = [input() for _ in range(n)]
inst = input()
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]
(sx, sy, ex, ey) = (-1, -1, -1, -1)
for i in range(n):
	for j in range(m):
		if g[i][j] == 'E':
			(ex, ey) = (i, j)
		if g[i][j] == 'S':
			(sx, sy) = (i, j)

def go(dirs):
	(cx, cy) = (sx, sy)
	for e in inst:
		cx += dx[dirs[int(e)]]
		cy += dy[dirs[int(e)]]
		if not (0 <= cx < n and 0 <= cy < m and (g[cx][cy] != '#')):
			return False
		if (cx, cy) == (ex, ey):
			return True
	return False
print(sum(map(go, permutations(range(4)))))


class Move:

	def __init__(self, dx, dy):
		self.dx = dx
		self.dy = dy

class Labyrinth:

	def __init__(self, width, height):
		self.width = width
		self.height = height
		self.start_x = 0
		self.start_y = 0
		self.final_x = 0
		self.final_y = 0
		self.cells = []
		self.commands = []

	def add_line(self, line: str):
		cells_in_line = []
		for i in range(len(line)):
			char = line[i]
			if char == '.':
				cells_in_line.append(True)
			elif char == '#':
				cells_in_line.append(False)
			elif char == 'S':
				cells_in_line.append(True)
				self.start_x = i
				self.start_y = len(self.cells)
			elif char == 'E':
				cells_in_line.append(True)
				self.final_x = i
				self.final_y = len(self.cells)
		self.cells.append(cells_in_line)

	def add_commands(self, line: str):
		for i in range(len(line)):
			self.commands.append(int(line[i]))

	def test(self, moves_case: list):
		pos_x = self.start_x
		pos_y = self.start_y
		for cmd_id in self.commands:
			move = moves_case[cmd_id]
			pos_x += move.dx
			pos_y += move.dy
			if pos_x == self.final_x and pos_y == self.final_y:
				return True
			if pos_x < 0 or pos_x >= self.width or pos_y < 0 or (pos_y >= self.height):
				return False
			if not self.cells[pos_y][pos_x]:
				return False
		return False
data = input().split()
lab = Labyrinth(int(data[1]), int(data[0]))
for y in range(lab.height):
	lab.add_line(input())
lab.add_commands(input())
move_up = Move(0, -1)
move_down = Move(0, 1)
move_left = Move(-1, 0)
move_right = Move(1, 0)

def gen_cases_3(m1, m2, m3):
	return [[m1, m2, m3], [m1, m3, m2], [m2, m1, m3], [m2, m3, m1], [m3, m1, m2], [m3, m2, m1]]
cases = []
for case in gen_cases_3(move_down, move_left, move_right):
	cases.append([move_up] + case)
for case in gen_cases_3(move_up, move_left, move_right):
	cases.append([move_down] + case)
for case in gen_cases_3(move_down, move_up, move_right):
	cases.append([move_left] + case)
for case in gen_cases_3(move_down, move_left, move_up):
	cases.append([move_right] + case)
good_cases = 0
for case in cases:
	if lab.test(case):
		good_cases += 1
print(good_cases)


(n, k) = map(int, input().strip().split(' '))
M = []
for i in range(n):
	M.append(input())
A = [[0, 1, 2, 3], [0, 1, 3, 2], [0, 2, 1, 3], [0, 2, 3, 1], [0, 3, 1, 2], [0, 3, 2, 1], [1, 0, 2, 3], [1, 0, 3, 2], [1, 2, 0, 3], [1, 2, 3, 0], [1, 3, 0, 2], [1, 3, 2, 0], [2, 1, 0, 3], [2, 1, 3, 0], [2, 0, 1, 3], [2, 0, 3, 1], [2, 3, 1, 0], [2, 3, 0, 1], [3, 1, 2, 0], [3, 1, 0, 2], [3, 2, 1, 0], [3, 2, 0, 1], [3, 0, 1, 2], [3, 0, 2, 1]]
L = list(input())
for i in range(len(L)):
	L[i] = int(L[i])
si = 0
sj = 0
ei = 0
ej = 0
for i in range(n):
	for j in range(k):
		if M[i][j] == 'S':
			si = i
			sj = j
		if M[i][j] == 'E':
			ei = i
			ej = j

def count(a, b, c, d, L):
	i = si
	j = sj
	for e in range(len(L)):
		if L[e] == a:
			i = i - 1
			if i < 0 or M[i][j] == '#':
				return False
		if L[e] == b:
			i = i + 1
			if i >= n or M[i][j] == '#':
				return False
		if L[e] == c:
			j = j + 1
			if j >= k or M[i][j] == '#':
				return False
		if L[e] == d:
			j = j - 1
			if j < 0 or M[i][j] == '#':
				return False
		if i == ei and j == ej:
			return True
	return False
sum = 0
for r in range(24):
	a = A[r][0]
	b = A[r][1]
	c = A[r][2]
	d = A[r][3]
	if count(a, b, c, d, L) == True:
		sum = sum + 1
print(sum)


import itertools
import sys
(n, m) = [int(x) for x in sys.stdin.readline().split()]
maze = []
robopos = None
for i in range(n):
	maze.append(sys.stdin.readline())
	if maze[i].find('S') != -1:
		robopos = [i, maze[i].find('S')]
directions = [int(x) for x in sys.stdin.readline()[:-1]]
howgo = [(-1, 0), (1, 0), (0, -1), (0, 1)]
escapes = 0
for howgoo in itertools.permutations(howgo):
	roboposs = robopos.copy()
	for d in directions:
		roboposs[0] += howgoo[d][0]
		roboposs[1] += howgoo[d][1]
		if roboposs[0] < 0 or roboposs[1] < 0 or roboposs[0] >= n or (roboposs[1] >= m):
			break
		if maze[roboposs[0]][roboposs[1]] == '#':
			break
		if maze[roboposs[0]][roboposs[1]] == 'E':
			escapes += 1
			break
print(escapes)


z = [(1, 0), (0, 1), (-1, 0), (0, -1)]
from itertools import permutations
z = permutations(z, 4)
(a, b) = map(int, input().split())
(x, y) = (0, 0)
o = []
for i in range(a):
	q = input()
	if 'S' in q:
		x = i
		y = q.index('S')
	o += [q]
code = input()

def mar(k, f, f1):
	global o, q, code, a, b
	x = f
	y = f1
	for i in code:
		s = k[int(i)]
		x += s[0]
		y += s[1]
		if x < 0 or y < 0 or x >= a or (y >= b) or (o[x][y] == '#'):
			return False
		if o[x][y] == 'E':
			return True
	return False
su = 0
for i in z:
	if mar(i, x, y):
		su += 1
print(su)


from collections import deque
import itertools
from sys import stdin
lines = deque((line.strip() for line in stdin.readlines()))

def nextline():
	return lines.popleft()

def types(cast, sep=None):
	return tuple((cast(x) for x in nextline().split(sep=sep)))

def ints(sep=None):
	return types(int, sep=sep)

def strs(sep=None):
	return nextline().split(sep=sep)

def main():
	(N, M) = ints()
	graph = list()
	start = (-1, -1)
	for i in range(N):
		graph.append(nextline())
		j = graph[i].find('S')
		if j != -1:
			start = (i, j)
	s = [int(ch) for ch in nextline()]
	dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]
	count = 0
	for perm in itertools.permutations(range(4)):
		(r, c) = start
		valid = True
		for cmd in s:
			d = dirs[perm[cmd]]
			r += d[0]
			c += d[1]
			if r < 0 or r >= N or c < 0 or (c >= M) or (graph[r][c] == '#'):
				valid = False
				break
			elif graph[r][c] == 'E':
				break
		if valid and graph[r][c] == 'E':
			count += 1
	print(count)
main()


from collections import namedtuple
import itertools
(n, m) = map(int, input().split())
Point = namedtuple('Point', 'i j')
start = None
end = None
isObs = [[False for x in range(m)] for y in range(n)]
for i in range(n):
	line = input()
	for j in range(m):
		if line[j] == '#':
			isObs[i][j] = True
		if line[j] == 'S':
			start = Point(i, j)
		if line[j] == 'E':
			end = Point(i, j)
instructions = input()
nums = ['0', '1', '2', '3']
dirs = itertools.permutations(['u', 'l', 'r', 'd'])
ways = 0
for perm in dirs:
	dirDict = dict(zip(nums, perm))
	(i, j) = (start[0], start[1])
	for ins in instructions:
		mov = dirDict[ins]
		if mov == 'u':
			i -= 1
		if mov == 'd':
			i += 1
		if mov == 'l':
			j -= 1
		if mov == 'r':
			j += 1
		if i < 0 or j < 0 or i >= n or (j >= m) or isObs[i][j]:
			break
		if i == end[0] and j == end[1]:
			ways += 1
			break
print(ways)


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)


import sys
import string
from collections import Counter, defaultdict
from math import fsum, sqrt, gcd, ceil, factorial
from operator import add
from itertools import permutations
inf = float('inf')
flush = lambda : sys.stdout.flush
comb = lambda x, y: factorial(x) // factorial(y) // factorial(x - y)
ip = lambda : input()
ii = lambda : int(input())
r = lambda : map(int, input().split())
rr = lambda : list(r())
(a, b) = r()
arr = [ip() for _ in range(a)]
s = ip()
x = permutations(list('0123'))
for i in range(a):
	for j in range(b):
		if arr[i][j] == 'S':
			start = (i, j)
		if arr[i][j] == 'E':
			end = (i, j)

def ok(u, d, l, r):
	(x, y) = start
	for i in s:
		if i == u:
			y += 1
		if i == d:
			y -= 1
		if i == r:
			x += 1
		if i == l:
			x -= 1
		if x < 0 or x == a or y < 0 or (y == b):
			return False
		if arr[x][y] == '#':
			return False
		if (x, y) == end:
			return True
	return False
c = 0
for i in x:
	if ok(*i):
		c += 1
print(c)


def gen():
	if len(kom) == 4:
		prov(kom)
		return
	for i in range(4):
		if kom1[i][0]:
			kom1[i][0] = False
			kom.append(kom1[i][1])
			gen()
			kom.pop()
			kom1[i][0] = True

def prov(kom):
	global k
	x = x0
	y = y0
	for i in s:
		p = int(i)
		x += kom[p][0]
		y += kom[p][1]
		if not m > x >= 0 or not n > y >= 0:
			return
		if a[y][x] == '#':
			return
		if a[y][x] == 'E':
			k += 1
			return
(n, m) = map(int, input().split())
a = [input() for i in range(n)]
s = input()
kom1 = [[True, (1, 0)], [True, (-1, 0)], [True, (0, 1)], [True, (0, -1)]]
for x0 in range(m):
	t = True
	for y0 in range(n):
		if a[y0][x0] == 'S':
			break
	else:
		t = False
	if t:
		break
k = 0
kom = []
gen()
print(k)


(n, m) = map(int, input().split())
g = [input() for i in range(n)]
(s, e) = ((0, 0), (n - 1, m - 1))
d = list(map(int, list(input())))
for i in range(n):
	for j in range(m):
		if g[i][j] == 'S':
			s = (i, j)
		if g[i][j] == 'E':
			e = (i, j)
t = 0
for d2 in range(4):
	for d3 in range(4):
		for d4 in range(4):
			for d5 in range(4):
				p = [d2, d3, d4, d5]
				if sorted(p) == [0, 1, 2, 3]:
					(x, y) = s
					i = 0
					while i < len(d) and 0 <= x < n and (0 <= y < m) and (g[x][y] not in ['E', '#']):
						r = p[d[i]]
						x += 1 if r == 0 else -1 if r == 1 else 0
						y += 1 if r == 2 else -1 if r == 3 else 0
						i += 1
					if 0 <= x < n and 0 <= y < m and (g[x][y] == 'E'):
						t += 1
print(t)


from itertools import permutations
(n, m) = map(int, input().split())
a = [list(input()) for i in range(n)]
s = list(map(int, input()))
ans = 0
permut = [list(i) for i in permutations([0, 1, 2, 3], 4)]
hod = [[-1, 0], [0, 1], [1, 0], [0, -1]]
for i in permut:
	now_h = [hod[i[0]], hod[i[1]], hod[i[2]], hod[i[3]]]
	for x in range(n):
		for y in range(m):
			if a[x][y] == 'S':
				(xs, ys) = (x, y)
			elif a[x][y] == 'E':
				(xe, ye) = (x, y)
	for now in s:
		xs += now_h[now][0]
		ys += now_h[now][1]
		if xs >= n or ys >= m or xs < 0 or (ys < 0) or (a[xs][ys] == '#'):
			break
		if a[xs][ys] == 'E':
			ans += 1
			break
print(ans)


import itertools
(n, m) = map(int, input().split())
a = []
for i in range(n):
	a.append(input())
	if 'S' in a[i]:
		sx = ps = a[i].index('S')
		sy = pss = i
p = input()
perm = list(itertools.permutations([(0, -1), (1, 0), (0, 1), (-1, 0)]))
t = 0
for aa in perm:
	sx = ps
	sy = pss
	for i in p:
		sx += aa[int(i)][0]
		sy += aa[int(i)][1]
		if sx >= m or sy >= n or sx < 0 or (sy < 0):
			break
		if a[sy][sx] == '#':
			break
		elif a[sy][sx] == 'E':
			t += 1
			break
print(t)


from itertools import permutations
(n, m) = map(int, input().split())
maze = []
for _ in range(n):
	maze.append(input())
instructions = input()
start_r = 0
start_c = 0
current_r = 0
current_c = 0

def find_start():
	for i in range(n):
		for j in range(m):
			if maze[i][j] == 'S':
				return (i, j)
(start_r, start_c) = find_start()

def move(direction):
	global current_r
	global current_c
	if direction == 0:
		if current_r == 0:
			return 0
		current_r -= 1
	if direction == 1:
		if current_r == n - 1:
			return 0
		current_r += 1
	if direction == 2:
		if current_c == 0:
			return 0
		current_c -= 1
	if direction == 3:
		if current_c == m - 1:
			return 0
		current_c += 1
	if maze[current_r][current_c] == '#':
		return 0
	if maze[current_r][current_c] == 'E':
		return 1
	return 2

def is_correct(per_list):
	global current_r
	global current_c
	(current_r, current_c) = (start_r, start_c)
	for inst in instructions:
		res = move(per_list[int(inst)])
		if res == 1:
			return True
		if res == 0:
			return False
	return False
ans = 0
for per in permutations([0, 1, 2, 3]):
	if is_correct(per):
		ans += 1
print(ans)


(n, m) = input().split()
n = int(n)
m = int(m)
iS = list()
iE = list()
maze = list()
for i in range(n):
	x = input()
	if 'S' in x:
		for j in range(len(x)):
			if 'S' == x[j]:
				iS.append(i)
				iS.append(j)
	if 'E' in x:
		for j in range(len(x)):
			if 'E' == x[j]:
				iE.append(i)
				iE.append(j)
	l = list()
	for i in range(len(x)):
		l.append(x[i])
	maze.append(l)
s = input()
count = 0
case = ['0123', '0132', '0213', '0231', '0312', '0321', '1230', '1203', '1302', '1320', '1032', '1023', '2301', '2310', '2013', '2031', '2103', '2130', '3012', '3021', '3102', '3120', '3201', '3210']
for i in range(len(case)):
	u = case[i][0]
	d = case[i][1]
	r = case[i][2]
	l = case[i][3]
	x = iS[0]
	y = iS[1]
	flag = 1
	for j in range(len(s)):
		if s[j] == u:
			x = x - 1
		elif s[j] == d:
			x = x + 1
		elif s[j] == r:
			y = y + 1
		elif s[j] == l:
			y = y - 1
		if x < 0 or x > n - 1 or y < 0 or (y > m - 1):
			break
		elif maze[x][y] == 'E':
			flag = 0
			break
		elif maze[x][y] == '#':
			break
	if flag == 0:
		count = count + 1
print(count)


import itertools
(n, m) = [int(i) for i in input().split()]
count = 0
a = []
for i in range(n):
	a.append([i for i in input()])
instr = input()
start = [0, 0]
end = [0, 0]

def follow(map):
	pos = [start[0], start[1]]
	for c in instr:
		move = map[c]
		if move == 'U':
			pos[0] -= 1
		if move == 'D':
			pos[0] += 1
		if move == 'L':
			pos[1] -= 1
		if move == 'R':
			pos[1] += 1
		if pos == end:
			return True
		if pos[0] < 0 or pos[0] >= n or pos[1] < 0 or (pos[1] >= m):
			return False
		if a[pos[0]][pos[1]] == '#':
			return False
	return False
for i in range(n):
	for j in range(m):
		if a[i][j] == 'S':
			start = [i, j]
		elif a[i][j] == 'E':
			end = [i, j]
for d in itertools.permutations('UDLR'):
	map = {'0': d[0], '1': d[1], '2': d[2], '3': d[3]}
	if follow(map):
		count += 1
print(count)


import sys
(n, m) = map(int, input().split())
a = ['' for i in range(n)]
for i in range(n):
	s = input()
	a[i] = s
startx = 0
starty = 0
x = 0
y = 0
endx = 0
endy = 0
for i in range(n):
	for j in range(m):
		if a[i][j] == 'S':
			startx = i
			starty = j
			x = i
			x = j
		elif a[i][j] == 'E':
			endx = i
			endy = j
t = input()
dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]
cnt = 0
for i in range(4):
	for j in range(4):
		for k in range(4):
			for p in range(4):
				q = [i, j, k, p]
				if len(list(set(q))) != len(q):
					continue
				x = startx
				y = starty
				f = 0
				for h in t:
					for g in range(4):
						if int(h) == q[g]:
							x += dx[g]
							y += dy[g]
							if x >= n or x < 0 or y >= m or (y < 0) or (a[x][y] == '#'):
								f = 1
								break
							elif a[x][y] == 'E':
								f = 1
								break
					if f:
						break
				if x >= n or x < 0 or y >= m or (y < 0) or (a[x][y] == '#'):
					continue
				if a[x][y] == 'E':
					cnt += 1
print(cnt)


import itertools
(n, m) = map(int, input().split())
maze = ['#' * (m + 2)] + ['#' + input() + '#' for _ in range(n)] + ['#' * (m + 2)]
moves = list(map(int, list(input())))
(x, y) = (None, None)
for (i, row) in enumerate(maze):
	if row.count('S'):
		(x, y) = (i, row.index('S'))

def traverse(x, y, mapping):
	for move in moves:
		x += mapping[move][0]
		y += mapping[move][1]
		if maze[x][y] == '#':
			return False
		if maze[x][y] == 'E':
			return True
	return False
mappings = list(itertools.permutations([[0, 1], [0, -1], [1, 0], [-1, 0]]))
print(sum([traverse(x, y, mapping) for mapping in mappings]))


(n, m) = map(int, input().split())
A = []
for q in range(n):
	a = input()
	B = []
	for w in range(m):
		if a[w] == 'S':
			x0 = w
			y0 = q
		B.append(a[w])
	A.append(B)
B = [0, 1, 2, 3]
count = 0
s = input()
for q in range(4):
	for w in range(4):
		if w == q:
			continue
		for e in range(4):
			if e == q or e == w:
				continue
			for r in range(4):
				if r == e or r == w or r == q:
					continue
				x = x0
				y = y0
				X = []
				Y = []
				for i in range(len(s)):
					mo = int(s[i])
					if mo == q:
						x = x + 1
					if mo == w:
						x = x - 1
					if mo == e:
						y = y + 1
					if mo == r:
						y = y - 1
					X.append(x)
					Y.append(y)
					if x < 0 or y < 0:
						break
					if x >= m or y >= n:
						break
					if A[y][x] == 'E':
						count = count + 1
						break
					if A[y][x] == '#':
						break
print(count)


from sys import stdin, stdout

def generateCases(caseList, case, index):
	if index > 3:
		caseList.append(tuple(case))
		return
	for c in 'UDLR':
		if c not in case:
			case.append(c)
			generateCases(caseList, case, index + 1)
			case.pop()

def dfs(moveStr, maze, endPoint, moveMap, row, col, index):
	if index > 0:
		if row < 0 or row >= len(maze) or col < 0 or (col >= len(maze[0])) or (maze[row][col] == '#'):
			return 0
		if (row, col) == endPoint:
			return 1
		if index >= len(moveStr):
			return 0
	num = int(moveStr[index])
	char = moveMap[num]
	if char is 'U':
		return dfs(moveStr, maze, endPoint, moveMap, row - 1, col, index + 1)
	elif char is 'D':
		return dfs(moveStr, maze, endPoint, moveMap, row + 1, col, index + 1)
	elif char is 'L':
		return dfs(moveStr, maze, endPoint, moveMap, row, col - 1, index + 1)
	elif char is 'R':
		return dfs(moveStr, maze, endPoint, moveMap, row, col + 1, index + 1)

def main():
	(n, m) = [int(x) for x in stdin.readline().strip().split()]
	maze = []
	for i in range(n):
		maze.append(stdin.readline().strip())
	moveStr = stdin.readline().strip()
	for i in range(n):
		for j in range(m):
			if maze[i][j] == 'S':
				startPoint = (i, j)
			if maze[i][j] == 'E':
				endPoint = (i, j)
	caseList = []
	generateCases(caseList, [], 0)
	cnt = 0
	for moveMap in caseList:
		cnt += dfs(moveStr, maze, endPoint, moveMap, startPoint[0], startPoint[1], 0)
	print(cnt)
main()


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)


import itertools
dir = [[-1, 0], [1, 0], [0, -1], [0, 1]]
(n, m) = list(map(int, input().split()))
s = list()
sy = -1
sx = -1
ey = -1
ex = -1
for i in range(0, n):
	a = input()
	s.append(a)
	for j in range(0, m):
		if a[j] == 'S':
			sy = i
			sx = j
		elif a[j] == 'E':
			ey = i
			ex = j
c = input()
ans = 0
for i in list(itertools.permutations(['0', '1', '2', '3'])):
	uy = sy
	ux = sx
	ok = 0
	for j in range(0, len(c)):
		idx = i.index(c[j])
		uy += dir[idx][0]
		ux += dir[idx][1]
		if uy < 0 or uy > n - 1 or ux < 0 or (ux > m - 1) or (s[uy][ux] == '#'):
			break
		elif s[uy][ux] == 'E':
			ok = 1
			break
	ans += ok
print(ans)


from itertools import permutations
(n, m) = map(int, input().strip().split(' '))
g = []
for i in range(n):
	g.append(input().strip())
seq = input().strip()
st_r = 0
st_c = 0
en_r = 0
en_c = 0
for i in range(n):
	for j in range(m):
		if g[i][j] == 'S':
			st_r = i
			st_c = j
		elif g[i][j] == 'E':
			en_r = i
			en_c = j

def check(p):
	f = dict()
	f[p[0]] = 'L'
	f[p[1]] = 'R'
	f[p[2]] = 'U'
	f[p[3]] = 'D'
	r = st_r
	c = st_c
	for cc in seq:
		inst = f[cc]
		if inst == 'L':
			c -= 1
		elif inst == 'R':
			c += 1
		elif inst == 'U':
			r -= 1
		else:
			r += 1
		if r < 0 or c < 0 or c >= m or (r >= n):
			return 0
		if g[r][c] == '#':
			return 0
		elif g[r][c] == 'E':
			return 1
	return 0
ans = 0
for p in permutations('0123'):
	if check(p):
		ans += 1
print(ans)


(n, m) = map(int, input().split())
a = []
for i in range(n):
	k = input()
	a.append(k)
	if k.find('S') > -1:
		stx = k.find('S')
		sty = i
	if k.find('E') > -1:
		endx = k.find('E')
		endy = i
cmd = input()
ans = 0
for p1 in range(4):
	for p2 in range(4):
		for p3 in range(4):
			for p4 in range(4):
				if p1 == p2 or p2 == p3 or p1 == p3 or (p1 == p4) or (p2 == p4) or (p3 == p4):
					continue
				else:
					x = stx
					y = sty
					for i in range(len(cmd)):
						if int(cmd[i]) == p1:
							x += 1
						if int(cmd[i]) == p2:
							x -= 1
						if int(cmd[i]) == p3:
							y += 1
						if int(cmd[i]) == p4:
							y -= 1
						if x < m and y < n and (x >= 0) and (y >= 0):
							if x == endx and y == endy:
								ans += 1
								break
							if a[y][x] == '#':
								break
						else:
							break
print(ans)


from itertools import permutations
(n, m) = map(int, input().split())
lab = '#' * (m + 2)
for n in range(n):
	lab += '#' + input() + '#'
lab += '#' * (m + 2)
s = input()
cmd = [ord(x) - 48 for x in s]
pers = permutations([1, -1, m + 2, -m - 2])
ans = 0
for per in pers:
	where = lab.find('S')
	for c in cmd:
		where += per[c]
		if lab[where] == 'E':
			ans += 1
			break
		if lab[where] == '#':
			break
print(ans)


(n, m) = map(int, input().split())
d = []
for i in range(n):
	d.append(input())
s = input()
cnt = 0
for i in range(n):
	for j in range(m):
		if 'S' == d[i][j]:
			(sc, sr) = (j, i)
		if 'E' == d[i][j]:
			(ec, er) = (j, i)
t = [0, 0, 0, 0]
for t[0] in range(4):
	for t[1] in range(4):
		for t[2] in range(4):
			for t[3] in range(4):
				if t[0] == t[1] or t[0] == t[2] or t[0] == t[3] or (t[1] == t[2]) or (t[1] == t[3]) or (t[2] == t[3]):
					continue
				else:
					c = sc
					r = sr
					for i in s:
						if t[ord(i) - 48] == 0:
							c += 1
						elif t[ord(i) - 48] == 1:
							c -= 1
						elif t[ord(i) - 48] == 2:
							r += 1
						else:
							r -= 1
						if c < 0 or c >= m or r < 0 or (r >= n):
							break
						if d[r][c] == '#':
							break
						if d[r][c] == 'E':
							cnt += 1
							break
print(cnt)


(n, m) = map(int, input().split())
a = []
k = 0
(s1, s2, e1, e2) = (0, 0, 0, 0)
for i in range(n):
	h = input()
	a.append(h)
	if 'S' in h:
		s1 = i
		s2 = h.index('S')
	if 'E' in h:
		e1 = i
		e2 = h.index('E')
d = input()
d1 = s1
d2 = s2
d3 = ['0', '1', '2', '3']
for j0 in d3:
	for j1 in d3:
		for j2 in d3:
			for j3 in d3:
				if j0 != j1 and j0 != j2 and (j0 != j3) and (j1 != j2) and (j1 != j3) and (j2 != j3):
					s1 = d1
					s2 = d2
					g = 0
					for i in range(len(d)):
						if d[i] == j0:
							s1 -= 1
						elif d[i] == j1:
							s1 += 1
						elif d[i] == j2:
							s2 -= 1
						elif d[i] == j3:
							s2 += 1
						if s1 < n and s1 >= 0 and (s2 >= 0) and (s2 < m) and (a[s1][s2] == 'E'):
							k += 1
							break
						elif (s1 >= n or s1 < 0 or s2 < 0 or (s2 >= m)) or (s1 < n and s1 >= 0 and (s2 >= 0) and (s2 < m) and (a[s1][s2] == '#')):
							break
print(k)


(n, m) = map(int, input().split())
maze = []
for i in range(n):
	maze.append(input())
s = input()
pos = ['0', '1', '2', '3']
cnt = 0
curr = -1
fin = -1
for i in range(len(maze)):
	for j in range(len(maze[0])):
		if maze[i][j] == 'S':
			curr = [i, j]
		elif maze[i][j] == 'E':
			fin = [i, j]
ini = curr.copy()
count = 0
for l in pos:
	pos2 = pos.copy()
	pos2.remove(l)
	for r in pos2:
		pos3 = pos2.copy()
		pos3.remove(r)
		for d in pos3:
			flag = False
			curr = ini.copy()
			for mov in s:
				if mov == l:
					curr[1] -= 1
				elif mov == r:
					curr[1] += 1
				elif mov == d:
					curr[0] += 1
				else:
					curr[0] -= 1
				if curr[0] < 0 or curr[1] < 0 or curr[0] == n or (curr[1] == m) or (maze[curr[0]][curr[1]] == '#'):
					flag = False
					break
				elif curr == fin:
					flag = True
					break
			if flag:
				count += 1
print(count)


(n, m) = map(int, input().split())
labList = []
for i in range(0, n):
	currentLine = list(map(str, input().split()))
	currentLine = list(currentLine[0])
	labList.append(currentLine)
s = list(map(str, input().split()))
s = list(s[0])
for a in range(0, len(s)):
	s[a] = int(s[a])
for i1 in range(0, n):
	for i2 in range(0, m):
		if labList[i1][i2] == 'S':
			startRiad = i1
			karmaRiad = startRiad
			startKolona = i2
			karmaKolona = startKolona
		elif labList[i1][i2] == 'E':
			endRiad = i1
			endKolona = i2
counter = 0
for a1 in range(0, 4):
	for a2 in range(0, 4):
		if a2 != a1:
			for a3 in range(0, 4):
				if a3 != a1 and a3 != a2:
					for a4 in range(0, 4):
						if a4 != a1 and a4 != a2 and (a4 != a3):
							startRiad = karmaRiad
							startKolona = karmaKolona
							for aye in range(0, len(s)):
								if s[aye] == a1:
									startRiad -= 1
									if startRiad < 0:
										break
									elif startKolona < 0:
										break
									elif startRiad >= n:
										break
									elif startKolona >= m:
										break
									elif labList[startRiad][startKolona] == '#':
										break
									elif startRiad == endRiad and startKolona == endKolona:
										counter += 1
										break
								elif s[aye] == a2:
									startRiad += 1
									if startRiad < 0:
										break
									elif startKolona < 0:
										break
									elif startRiad >= n:
										break
									elif startKolona >= m:
										break
									elif labList[startRiad][startKolona] == '#':
										break
									elif startRiad == endRiad and startKolona == endKolona:
										counter += 1
										break
								elif s[aye] == a3:
									startKolona += 1
									if startRiad < 0:
										break
									elif startKolona < 0:
										break
									elif startRiad >= n:
										break
									elif startKolona >= m:
										break
									elif labList[startRiad][startKolona] == '#':
										break
									elif startRiad == endRiad and startKolona == endKolona:
										counter += 1
										break
								elif s[aye] == a4:
									startKolona -= 1
									if startRiad < 0:
										break
									elif startKolona < 0:
										break
									elif startRiad >= n:
										break
									elif startKolona >= m:
										break
									elif labList[startRiad][startKolona] == '#':
										break
									elif startRiad == endRiad and startKolona == endKolona:
										counter += 1
										break
print(counter)


import sys
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, 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)


perm = ['UDRL', 'UDLR', 'URDL', 'URLD', 'ULRD', 'ULDR', 'DURL', 'DULR', 'DRUL', 'DRLU', 'DLRU', 'DLUR', 'RDUL', 'RDLU', 'RUDL', 'RULD', 'RLUD', 'RLDU', 'LDRU', 'LDUR', 'LRDU', 'LRUD', 'LURD', 'LUDR']
bla = input()
bla = bla.split()
n = int(bla[0])
m = int(bla[1])
g = []
for i in range(n):
	temp = input()
	g.append(temp)
	for j in range(len(temp)):
		if temp[j] == 'S':
			si = i
			sj = j
		if temp[j] == 'E':
			ei = i
			ej = j
s = input()
cnt = 0
i = si
j = sj
for mp in perm:
	flag = 1
	i = si
	j = sj
	for dir in s:
		if flag == 1:
			if mp[int(dir)] == 'U':
				if i != 0:
					if g[i - 1][j] != '#':
						i -= 1
					else:
						flag = 0
				else:
					flag = 0
			elif mp[int(dir)] == 'D':
				if i != n - 1:
					if g[i + 1][j] != '#':
						i += 1
					else:
						flag = 0
				else:
					flag = 0
			elif mp[int(dir)] == 'L':
				if j != 0:
					if g[i][j - 1] != '#':
						j -= 1
					else:
						flag = 0
				else:
					flag = 0
			elif mp[int(dir)] == 'R':
				if j != m - 1:
					if g[i][j + 1] != '#':
						j += 1
					else:
						flag = 0
				else:
					flag = 0
			if g[i][j] == 'E':
				cnt += 1
				flag = 0
print(cnt)


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)


(n, m) = [int(z) for z in input().split()]
a = [[z for z in input()] for i in range(n)]
for i in range(n):
	for j in range(m):
		if a[i][j] == 'S':
			stri = i
			strj = j
			break
way = input()
b = []
for i in range(4):
	for j in range(4):
		if j == i:
			continue
		for k in range(4):
			if k == j or k == i:
				continue
			for g in range(4):
				if g == j or g == i or g == k:
					continue
				b.append([str(i), str(j), str(k), str(g)])

def isgood(i, j):
	return 0 <= i < n and 0 <= j < m

def check(z):
	i = stri
	j = strj
	tmp = b[z]
	for l in way:
		if tmp.index(l) == 0:
			i += 1
			if isgood(i, j):
				if a[i][j] == '#':
					return 0
				if a[i][j] == 'E':
					return 1
			else:
				return 0
		elif tmp.index(l) == 1:
			i -= 1
			if isgood(i, j):
				if a[i][j] == '#':
					return 0
				if a[i][j] == 'E':
					return 1
			else:
				return 0
		elif tmp.index(l) == 2:
			j -= 1
			if isgood(i, j):
				if a[i][j] == '#':
					return 0
				if a[i][j] == 'E':
					return 1
			else:
				return 0
		elif tmp.index(l) == 3:
			j += 1
			if isgood(i, j):
				if a[i][j] == '#':
					return 0
				if a[i][j] == 'E':
					return 1
			else:
				return 0
	return 0
cnt = 0
for i in range(24):
	cnt += check(i)
print(cnt)


dirs = 'DLUR'
import itertools
(n, m) = [int(i) for i in input().split(' ')]
maze = []
for i in range(n):
	maze.append(input())
	if 'S' in maze[i]:
		ry = i
		rx = maze[i].index('S')
path = input()
ct = 0
for d in itertools.permutations(dirs):
	direction = {'0': d[0], '1': d[1], '2': d[2], '3': d[3]}
	(x, y) = (rx, ry)
	current = ''
	good = True
	for c in path:
		if direction[c] == 'U':
			y -= 1
		elif direction[c] == 'D':
			y += 1
		elif direction[c] == 'L':
			x -= 1
		elif direction[c] == 'R':
			x += 1
		if y >= len(maze) or y < 0:
			break
		elif x >= len(maze[y]) or x < 0:
			break
		elif maze[y][x] == '#':
			break
		elif maze[y][x] == 'E':
			ct += 1
			break
print(ct)


from itertools import permutations

def inside(x, y, n, m):
	return 0 <= x < n and 0 <= y < m
(n, m) = list(map(int, input().split()))
maze = []
for i in range(n):
	maze.append(input())
cmd = list(map(int, input()))
DX = [1, 0, -1, 0]
DY = [0, 1, 0, -1]
CMD2DIR = list(permutations(range(4)))
(y0, x0) = max([(maze[x].find('S'), x) for x in range(n)])
ans = 0
for cmd2dir in CMD2DIR:
	(x, y) = (x0, y0)
	for c in cmd:
		x += DX[cmd2dir[c]]
		y += DY[cmd2dir[c]]
		if not inside(x, y, n, m) or maze[x][y] == '#':
			break
		if maze[x][y] == 'E':
			ans += 1
			break
print(ans)


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) = [int(i) for i in input().split()]
maps = []
for i in range(n):
	maps.append([])
	s = input()
	for z in range(m):
		maps[i].append(s[z])
		if s[z] == 'S':
			bx = z
			by = i
		elif s[z] == 'E':
			fx = z
			fy = i
command = input()

def req(s, a):
	if len(s) == 4:
		ans.append(s)
		return
	for i in a:
		req(s + str(i), a - set([i]))
ans = []
setA = {0, 1, 2, 3}
req('', setA)
count = 0
for i in ans:
	(x, y) = (bx, by)
	f = True
	for z in command:
		if i.index(z) == 0:
			y -= 1
		elif i.index(z) == 1:
			y += 1
		elif i.index(z) == 2:
			x += 1
		else:
			x -= 1
		if not (x >= 0 and y >= 0 and (x < m) and (y < n) and (maps[y][x] != '#')):
			f = False
			break
		elif maps[y][x] == 'E':
			count += 1
			break
print(count)


mod = 1000000007
ii = lambda : int(input())
si = lambda : input()
dgl = lambda : list(map(int, input()))
f = lambda : map(int, input().split())
il = lambda : list(map(int, input().split()))
ls = lambda : list(input())
from itertools import *
d = dict()
(n, m) = f()
l = []
(sr, sc, er, ec) = (0, 0, 0, 0)
for i in range(n):
	x = si()
	if 'S' in x:
		sr = i
		sc = x.find('S')
	if 'E' in x:
		er = i
		ec = x.find('E')
	l.append(x)
s = si()
c = 0
perm = list(permutations('0123'))
for i in perm:
	(d[i[0]], d[i[1]], d[i[2]], d[i[3]]) = ('L', 'R', 'U', 'D')
	x = sr
	y = sc
	for j in s:
		if d[j] == 'L':
			y -= 1
		elif d[j] == 'R':
			y += 1
		elif d[j] == 'U':
			x -= 1
		else:
			x += 1
		if not -1 < x < n or not -1 < y < m or l[x][y] == '#':
			break
		if x == er and y == ec:
			c += 1
			break
print(c)


from itertools import permutations

def main():
	(N, M) = map(int, input().split())
	T = tuple((input() for _ in [0] * N))
	S = input()
	for (i, j) in enumerate(T):
		k = j.find('S')
		if k > -1:
			start = (i, k)
		k = j.find('E')
		if k > -1:
			end = (i, k)
	mapping = ((0, -1), (0, 1), (-1, 0), (1, 0))
	cnt = 0
	for i in permutations(mapping, 4):
		now = start
		for j in S:
			p = i[int(j)]
			x = now[0] + p[0]
			y = now[1] + p[1]
			if not 0 <= x < N or not 0 <= y < M:
				break
			now = (x, y)
			if now == end:
				cnt += 1
				break
			elif T[x][y] == '#':
				break
	print(cnt)
main()


(n, m) = map(int, input().split())
a = []
a.append('#' * (m + 2))
for i in range(n):
	s = input()
	for j in range(m):
		if s[j] == 'S':
			g = i + 1
			h = j + 1
	a.append('#' + s + '#')
a.append('#' * (m + 2))
b = []
b.append(['U', 'D', 'R', 'L'])
b.append(['U', 'D', 'L', 'R'])
b.append(['U', 'R', 'L', 'D'])
b.append(['U', 'R', 'D', 'L'])
b.append(['U', 'L', 'D', 'R'])
b.append(['U', 'L', 'R', 'D'])
b.append(['D', 'U', 'R', 'L'])
b.append(['D', 'U', 'L', 'R'])
b.append(['D', 'R', 'L', 'U'])
b.append(['D', 'R', 'U', 'L'])
b.append(['D', 'L', 'U', 'R'])
b.append(['D', 'L', 'R', 'U'])
b.append(['L', 'U', 'R', 'D'])
b.append(['L', 'U', 'D', 'R'])
b.append(['L', 'R', 'D', 'U'])
b.append(['L', 'R', 'U', 'D'])
b.append(['L', 'D', 'U', 'R'])
b.append(['L', 'D', 'R', 'U'])
b.append(['R', 'U', 'D', 'L'])
b.append(['R', 'U', 'L', 'D'])
b.append(['R', 'D', 'L', 'U'])
b.append(['R', 'D', 'U', 'L'])
b.append(['R', 'L', 'U', 'D'])
b.append(['R', 'L', 'D', 'U'])
s = input()
l = len(s)
z = 0
for i in range(24):
	x = g
	y = h
	for j in range(l):
		p = int(s[j])
		if b[i][p] == 'U':
			x += 1
		elif b[i][p] == 'D':
			x -= 1
		elif b[i][p] == 'L':
			y -= 1
		else:
			y += 1
		if a[x][y] == 'E':
			z += 1
			break
		if a[x][y] == '#':
			break
print(z)


(n, m) = [int(x) for x in input().split()]
maze = []
for i in range(n):
	row = input()
	maze.append([])
	for j in range(m):
		maze[i].append(row[j])
path = input()
possible = [{0: 'U', 1: 'D', 2: 'L', 3: 'R'}, {0: 'U', 1: 'D', 2: 'R', 3: 'L'}, {0: 'U', 1: 'L', 2: 'D', 3: 'R'}, {0: 'U', 1: 'L', 2: 'R', 3: 'D'}, {0: 'U', 1: 'R', 2: 'L', 3: 'D'}, {0: 'U', 1: 'R', 2: 'D', 3: 'L'}, {0: 'D', 1: 'U', 2: 'L', 3: 'R'}, {0: 'D', 1: 'U', 2: 'R', 3: 'L'}, {0: 'D', 1: 'L', 2: 'U', 3: 'R'}, {0: 'D', 1: 'L', 2: 'R', 3: 'U'}, {0: 'D', 1: 'R', 2: 'L', 3: 'U'}, {0: 'D', 1: 'R', 2: 'U', 3: 'L'}, {0: 'L', 1: 'D', 2: 'U', 3: 'R'}, {0: 'L', 1: 'D', 2: 'R', 3: 'U'}, {0: 'L', 1: 'U', 2: 'D', 3: 'R'}, {0: 'L', 1: 'U', 2: 'R', 3: 'D'}, {0: 'L', 1: 'R', 2: 'U', 3: 'D'}, {0: 'L', 1: 'R', 2: 'D', 3: 'U'}, {0: 'R', 1: 'D', 2: 'L', 3: 'U'}, {0: 'R', 1: 'D', 2: 'U', 3: 'L'}, {0: 'R', 1: 'L', 2: 'D', 3: 'U'}, {0: 'R', 1: 'L', 2: 'U', 3: 'D'}, {0: 'R', 1: 'U', 2: 'L', 3: 'D'}, {0: 'R', 1: 'U', 2: 'D', 3: 'L'}]

def trypath(mapping):
	truepath = ''
	for ch in path:
		truepath += mapping[int(ch)]
	for i in range(n):
		for j in range(m):
			if maze[i][j] == 'S':
				(x, y) = (i, j)
	for move in truepath:
		if move == 'U':
			(x, y) = (x - 1, y)
		if move == 'D':
			(x, y) = (x + 1, y)
		if move == 'L':
			(x, y) = (x, y - 1)
		if move == 'R':
			(x, y) = (x, y + 1)
		if x < 0 or x >= n or y < 0 or (y >= m) or (maze[x][y] == '#'):
			return 0
		if maze[x][y] == 'E':
			return 1
	return 0
ctr = 0
for mapping in possible:
	ctr += trypath(mapping)
print(ctr)


(n, m) = list(map(int, input().split()))
table = [input() for _ in range(n)]
instruction = list(map(int, list(input())))
out = 0
start = [0, 0]
for i in range(n):
	if 'S' in table[i]:
		start[0] = i
		start[1] = table[i].index('S')
combinations = [{0: 'U', 1: 'D', 2: 'L', 3: 'R'}, {0: 'U', 1: 'D', 2: 'R', 3: 'L'}, {0: 'U', 1: 'R', 2: 'L', 3: 'D'}, {0: 'U', 1: 'R', 2: 'D', 3: 'L'}, {0: 'U', 1: 'L', 2: 'D', 3: 'R'}, {0: 'U', 1: 'L', 2: 'R', 3: 'D'}, {0: 'D', 1: 'L', 2: 'U', 3: 'R'}, {0: 'D', 1: 'L', 2: 'R', 3: 'U'}, {0: 'D', 1: 'R', 2: 'U', 3: 'L'}, {0: 'D', 1: 'R', 2: 'L', 3: 'U'}, {0: 'D', 1: 'U', 2: 'R', 3: 'L'}, {0: 'D', 1: 'U', 2: 'L', 3: 'R'}, {0: 'L', 1: 'D', 2: 'U', 3: 'R'}, {0: 'L', 1: 'D', 2: 'R', 3: 'U'}, {0: 'L', 1: 'R', 2: 'U', 3: 'D'}, {0: 'L', 1: 'R', 2: 'D', 3: 'U'}, {0: 'L', 1: 'U', 2: 'D', 3: 'R'}, {0: 'L', 1: 'U', 2: 'R', 3: 'D'}, {0: 'R', 1: 'D', 2: 'L', 3: 'U'}, {0: 'R', 1: 'D', 2: 'U', 3: 'L'}, {0: 'R', 1: 'L', 2: 'D', 3: 'U'}, {0: 'R', 1: 'L', 2: 'U', 3: 'D'}, {0: 'R', 1: 'U', 2: 'L', 3: 'D'}, {0: 'R', 1: 'U', 2: 'D', 3: 'L'}]
for j in combinations:
	pos = start[:]
	for k in instruction:
		todo = j[k]
		if todo == 'U':
			pos[0] += 1
		if todo == 'D':
			pos[0] -= 1
		if todo == 'L':
			pos[1] -= 1
		if todo == 'R':
			pos[1] += 1
		if pos[0] == n or pos[0] == -1:
			break
		if pos[1] == m or pos[1] == -1:
			break
		if table[pos[0]][pos[1]] == '#':
			break
		if table[pos[0]][pos[1]] == 'E':
			out += 1
			break
print(out)


(n, m) = map(int, input().split())
maze = []
for i in range(n):
	s = input()
	maze.append(s)
route = input()
(Si, Sj, f) = (0, 0, 1)
for i in range(n):
	for j in range(m):
		if maze[i][j] == 'S':
			Si = i
			Sj = j
			f = 0
			break
	if f == 0:
		break

def check(l, r, u, d):
	(i, j) = (Si, Sj)
	for mk in route:
		mk = int(mk)
		if mk == l:
			i -= 1
		elif mk == r:
			i += 1
		elif mk == u:
			j -= 1
		elif mk == d:
			j += 1
		if i < 0 or j < 0 or i >= n or (j >= m) or (maze[i][j] == '#'):
			return 0
		if maze[i][j] == 'E':
			return 1
	if maze[i][j] == 'E':
		return 1
	else:
		return 0
perm = 0
import itertools
ls = [list(l) for l in list(itertools.permutations([0, 1, 2, 3]))]
for mk in ls:
	if check(mk[0], mk[1], mk[2], mk[3]) == 1:
		perm += 1
print(perm)


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) = 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()


(N, M) = map(int, input().split())
matrix = []
(s_x, s_y) = (0, 0)
for y in range(N):
	line = list(input())
	matrix.append(line)
	if 'S' in line:
		s_y = y
		s_x = line.index('S')
orders = list(input())

def get_dir(x):
	if x == 0:
		return (1, 0)
	if x == 1:
		return (-1, 0)
	if x == 2:
		return (0, 1)
	if x == 3:
		return (0, -1)

def test_dirs(dirs):
	(x, y) = (s_x, s_y)
	for order in orders:
		order = dirs[int(order)]
		x += order[0]
		y += order[1]
		if x < 0 or y < 0 or x >= M or (y >= N) or (matrix[y][x] == '#'):
			return 0
		if matrix[y][x] == 'E':
			return 1
	return 0
count = 0
dirs = [(0, 0)] * 4
for i1 in range(4):
	dirs[0] = get_dir(i1)
	for i2 in range(4):
		dirs[1] = get_dir(i2)
		for i3 in range(4):
			dirs[2] = get_dir(i3)
			for i4 in range(4):
				dirs[3] = get_dir(i4)
				if len([i1, i2, i3, i4]) == len(set([i1, i2, i3, i4])):
					count += test_dirs(dirs)
print(count)


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 = [['0'] * (m + 2)]
for i in range(n):
	a.append(['0'] + list(input()) + ['0'])
a.append(['0'] * (m + 2))
s = input()
(x, y) = (-1, -1)
for i in range(1, n + 1):
	for j in range(1, m + 1):
		if a[i][j] == 'S':
			(x, y) = (i, j)
k = 0
for u in range(4):
	for d in range(4):
		if d != u:
			for l in range(4):
				if l != u and l != d:
					for r in range(4):
						if r != l and r != u and (r != d):
							(p, q) = (x, y)
							for i in s:
								if int(i) == u:
									p -= 1
								if int(i) == d:
									p += 1
								if int(i) == l:
									q -= 1
								if int(i) == r:
									q += 1
								if a[p][q] == '0' or a[p][q] == '#' or a[p][q] == 'E':
									break
							if a[p][q] == 'E':
								k += 1
print(k)


from itertools import permutations
(rows_nr, cols_nr) = (int(x) for x in input().split())
r_c___val = []
start_r_c = [-1, -1]
for r in range(rows_nr):
	c___val = input()
	if 'S' in c___val:
		start_r_c[0] = r
		for (c, val) in enumerate(c___val):
			if val == 'S':
				start_r_c[1] = c
				break
	r_c___val.append(list(c___val))
commands = list(input())
ans = 0
start_arrange = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for permutation in permutations(start_arrange):
	curr_pos = start_r_c.copy()
	flag = True
	for sym in commands:
		command = int(sym)
		curr_pos[0] += permutation[command][0]
		curr_pos[1] += permutation[command][1]
		if curr_pos[0] < 0 or curr_pos[1] < 0:
			flag = False
		if curr_pos[0] >= rows_nr or curr_pos[1] >= cols_nr:
			flag = False
		if not flag:
			break
		if r_c___val[curr_pos[0]][curr_pos[1]] == '#':
			flag = False
			break
		if r_c___val[curr_pos[0]][curr_pos[1]] == 'E':
			break
	if flag and r_c___val[curr_pos[0]][curr_pos[1]] == 'E':
		ans += 1
print(ans)


from itertools import permutations

def index_2d(myList, v):
	for (i, x) in enumerate(myList):
		if v in x:
			return [i, x.index(v)]

def check_valid(D, L, U, R, s, a, n, m):
	start_pos = index_2d(a, 'S')
	end_pos = index_2d(a, 'E')
	curr_pos = start_pos
	for i in s:
		if i == D:
			curr_pos[0] += 1
			if curr_pos[0] >= n or a[curr_pos[0]][curr_pos[1]] == '#':
				return 0
		if i == L:
			curr_pos[1] -= 1
			if curr_pos[1] < 0 or a[curr_pos[0]][curr_pos[1]] == '#':
				return 0
		if i == U:
			curr_pos[0] -= 1
			if curr_pos[0] < 0 or a[curr_pos[0]][curr_pos[1]] == '#':
				return 0
		if i == R:
			curr_pos[1] += 1
			if curr_pos[1] >= m or a[curr_pos[0]][curr_pos[1]] == '#':
				return 0
		if curr_pos == end_pos:
			return 1
	return 0

def robo(a, s, n, m):
	l = list(permutations(range(4)))
	c = 0
	for i in l:
		(D, L, U, R) = i
		c += check_valid(D, L, U, R, s, a, n, m)
	return c
(n, m) = list(map(int, input().split()))
a = []
for i in range(n):
	a.append(list(input()))
s = list(map(int, input()))
print(robo(a, s, n, m))


import itertools
import collections

def outside(x, y):
	if x < 0 or x >= r or y < 0 or (y >= c):
		return True
	else:
		return False
dx = (0, 0, 1, -1)
dy = (1, -1, 0, 0)
s = input().split()
(r, c) = map(int, s)
m = []
for i in range(r):
	m.append(input())
S = [0, 0]
for i in range(r):
	if m[i].find('S') != -1:
		S = [i, m[i].find('S')]
		break
step = input()
ans = 0
for d in itertools.permutations([0, 1, 2, 3]):
	(x, y) = S
	for j in step:
		k = int(j)
		x += dx[d[k]]
		y += dy[d[k]]
		if outside(x, y) or m[x][y] == '#':
			break
		if m[x][y] == 'E':
			ans += 1
			break
print(ans)


import itertools
n = list(map(int, input().split(' ')))
b = []
sind = []
eind = []
obst = []
for i in range(n[0]):
	asdf = input()
	b.append([])
	for j in range(n[1]):
		if asdf[j] == 'S':
			sind = [i, j]
		elif asdf[j] == 'E':
			eind = [i, j]
		elif asdf[j] == '#':
			obst.append([i, j])

def add(x, y):
	return [x[0] + y[0], x[1] + y[1]]
perm = list(itertools.permutations([0, 1, 2, 3]))
inst = list(map(int, list(input())))
d = [[0, 1], [0, -1], [1, 0], [-1, 0]]
s = 0
for i in perm:
	find = dict([(i[0], d[0]), (i[1], d[1]), (i[2], d[2]), (i[3], d[3])])
	dead = False
	fin = False
	bot = [sind[0], sind[1]]
	for j in inst:
		if not dead:
			bot = add(bot, find[j])
			if bot[0] >= n[0] or bot[1] >= n[1] or bot[0] < 0 or (bot[1] < 0) or (bot in obst):
				dead = True
				break
			elif bot == eind:
				fin = True
				break
	if fin and (not dead):
		s += 1
print(s)


from itertools import permutations
(n, m) = (int(c) for c in input().split())
s = '#' * (m + 2)
for i in range(n):
	s += '#' + input().strip() + '#'
s += '#' * (m + 2)
ins = ['0123'.find(c) for c in input().strip()]
c = 0
for d in permutations([1, -1, m + 2, -m - 2]):
	p = s.find('S')
	for i in ins:
		p += d[i]
		if s[p] == 'E':
			c += 1
		if s[p] in 'E#':
			break
print(c)


from itertools import permutations
p = [[0, 1], [1, 0], [0, -1], [-1, 0]]
(n, m) = map(int, input().split())
a = []
(s, e) = ([], [])
for i in range(n):
	a.append([])
	for (j, v) in enumerate(input()):
		if v == 'S':
			s = [i, j]
		elif v == 'E':
			e = [i, j]
		if v == '#':
			a[i].append(False)
		else:
			a[i].append(True)
l = input()
c = 0
for i in permutations(p):
	(x, y) = s
	for l1 in l:
		j = i[int(l1)]
		x -= j[0]
		y -= j[1]
		if [x, y] == e:
			c += 1
			break
		if not 0 <= x < n or not 0 <= y < m:
			break
		if not a[x][y]:
			break
print(c)


(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)


res = 0
(n, m) = map(int, input().split())
a = ['#' * (m + 2)] + ['#' + input() + '#' for i in range(n)] + ['#' * (m + 2)]
s = input()
start = []
fin = []
for i in range(n + 2):
	for j in range(m + 2):
		if a[i][j] == 'S':
			start = [i, j]
		if a[i][j] == 'E':
			fin = [i, j]

def gen(pr):
	global res
	if len(pr) == 4:
		cur = start[:]
		for i in s:
			if pr[int(i)] == 0:
				cur[0] += 1
			if pr[int(i)] == 1:
				cur[0] -= 1
			if pr[int(i)] == 2:
				cur[1] += 1
			if pr[int(i)] == 3:
				cur[1] -= 1
			if a[cur[0]][cur[1]] == '#':
				break
			if cur[0] == fin[0] and cur[1] == fin[1]:
				res += 1
				break
	else:
		for i in range(4):
			if i not in pr:
				gen(pr + [i])
gen([])
print(res)


from itertools import permutations
n = 0
m = 0
grid = []
path = ''
ct = 0
direc = []
bas = [0, 1, 2, 3]
s_x = 0
s_y = 0
e_x = 0
e_y = 0
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def io():
	global n, m, grid, path
	(n, m) = map(int, input().split(' '))
	for i in range(0, n, 1):
		grid.append(input())
	path = input()

def preprocess():
	global s_x, s_y, e_x, e_y
	for i in range(0, n, 1):
		for j in range(0, m, 1):
			if grid[i][j] == 'S':
				s_x = i
				s_y = j
			elif grid[i][j] == 'E':
				e_x = i
				e_y = j

def reached():
	curr_x = s_x
	curr_y = s_y
	for d in path:
		ind = direc[int(d) - 0]
		curr_x += dx[ind]
		curr_y += dy[ind]
		if curr_x < 0 or curr_x >= n or curr_y < 0 or (curr_y >= m):
			return False
		elif grid[curr_x][curr_y] == '#':
			return False
		elif grid[curr_x][curr_y] == 'E':
			return True
	return False

def main():
	global ct, direc, bas
	io()
	preprocess()
	for subset in permutations(bas, 4):
		direc = subset
		if reached():
			ct += 1
	print(str(ct))
main()


from itertools import *
(n, m) = map(int, input().split())
p = [[0] * (m + 1) for i in range(n)] + [[0] * m]
for i in range(n):
	for (j, q) in enumerate(input()):
		if q == 'S':
			(a, b) = (i, j)
		p[i][j] = '#E'.find(q)
s = list(map(int, input()))

def f(d):
	(x, y) = (a, b)
	for k in s:
		(i, j) = d[k]
		x += i
		y += j
		if p[x][y] + 1:
			return p[x][y]
	return 0
t = [(1, 0), (-1, 0), (0, 1), (0, -1)]
print(sum((f(d) for d in permutations(t))))


from itertools import permutations
(n, m) = [int(c) for c in input().split(' ')]
b = [input() for _ in range(n)]
(x0, y0) = [None] * 2
for i in range(n):
	for j in range(m):
		if b[i][j] == 'S':
			(y0, x0) = (i, j)
s = input()
d = 'UDLR'
ans = 0
for p in permutations(d):
	(y, x) = (y0, x0)
	for step in s:
		move = p[int(step)]
		if move == 'U':
			y -= 1
		elif move == 'D':
			y += 1
		elif move == 'L':
			x -= 1
		elif move == 'R':
			x += 1
		if x < 0 or x >= m or y < 0 or (y >= n) or (b[y][x] == '#'):
			break
		if b[y][x] == 'E':
			ans += 1
			break
print(ans)


(n, m) = map(int, input().split())
list1 = [[] for i in range(n)]
for i in range(n):
	s = input()
	for j in range(m):
		list1[i].append(s[j])
for i in range(n):
	for j in range(m):
		if list1[i][j] == 'S':
			(i1, j1) = (i, j)
			break
s = input()
(a, b) = (i1, j1)
ans = 0
flag = True
for i in range(4):
	for j in range(4):
		if i != j:
			for q in range(4):
				if i != q and j != q:
					for w in range(4):
						if i != w and j != w and (q != w):
							(i1, j1, flag) = (a, b, True)
							for p in range(len(s)):
								if s[p] == str(i):
									if i1 > 0:
										if list1[i1 - 1][j1] != '#':
											i1 -= 1
										else:
											flag = False
											break
									else:
										flag = False
										break
								elif s[p] == str(j):
									if i1 + 1 <= n - 1:
										if list1[i1 + 1][j1] != '#':
											i1 += 1
										else:
											flag = False
											break
									else:
										flag = False
										break
								elif s[p] == str(q):
									if j1 > 0:
										if list1[i1][j1 - 1] != '#':
											j1 -= 1
										else:
											flag = False
											break
									else:
										flag = False
										break
								elif s[p] == str(w):
									if j1 + 1 <= m - 1:
										if list1[i1][j1 + 1] != '#':
											j1 += 1
										else:
											flag = False
											break
									else:
										flag = False
										break
								if list1[i1][j1] == 'E' and flag:
									ans += 1
									break
print(ans)


(n, m) = [int(n) for n in input().split()]
mat = []
arr = []
for i in range(n):
	s1 = input()
	arr = list(s1)
	mat.append(arr)
	arr = []
s = input()
count = 0
for i in range(n):
	for j in range(m):
		if mat[i][j] == 'S':
			start = [i, j]
		if mat[i][j] == 'E':
			end = [i, j]
r = [[0, 1], [0, -1], [-1, 0], [1, 0]]
for i in r:
	for j in r:
		if j == i:
			continue
		for k in r:
			if k == j or k == i:
				continue
			for l in r:
				if l == k or l == j or l == i:
					continue
				x = start[0]
				y = start[1]
				counter = 0
				for u in s:
					if u == '3':
						if x + l[0] >= n or x + l[0] < 0:
							break
						x = x + l[0]
						if y + l[1] >= m or y + l[1] < 0:
							break
						y = y + l[1]
						if mat[x][y] == '#':
							break
					if u == '2':
						if x + k[0] >= n or x + k[0] < 0:
							break
						x = x + k[0]
						if y + k[1] >= m or y + k[1] < 0:
							break
						y = y + k[1]
						if mat[x][y] == '#':
							break
					if u == '1':
						if x + j[0] >= n or x + j[0] < 0:
							break
						x = x + j[0]
						if y + j[1] >= m or y + j[1] < 0:
							break
						y = y + j[1]
						if mat[x][y] == '#':
							break
					if u == '0':
						if x + i[0] >= n or x + i[0] < 0:
							break
						x = x + i[0]
						if y + i[1] >= m or y + i[1] < 0:
							break
						y = y + i[1]
						if mat[x][y] == '#':
							break
					counter = counter + 1
					if mat[x][y] == 'E':
						count = count + 1
						break
print(count)


(n, m) = map(int, input().split())
a = []
for i in range(n):
	temp = input()
	a.append(temp)
s = input()
lst = [0, 1, 2, 3]

def permutation(lst):
	if len(lst) == 0:
		return []
	if len(lst) == 1:
		return [lst]
	l = []
	for i in range(len(lst)):
		m = lst[i]
		remLst = lst[:i] + lst[i + 1:]
		for p in permutation(remLst):
			l.append([m] + p)
	return l
ans = 0
for i in range(n):
	flag = 1
	for j in range(m):
		if a[i][j] == 'S':
			flag = 0
			break
	if not flag:
		break
p1 = i
p2 = j
perms = permutation(lst)
for i in perms:
	flag = False
	start = [p1, p2]
	for j in s:
		if int(j) == i[0]:
			if start[1] == 0:
				break
			start[1] -= 1
			if a[start[0]][start[1]] == 'E':
				flag = True
				break
			elif a[start[0]][start[1]] == '#':
				break
		elif int(j) == i[1]:
			if start[1] == m - 1:
				flag = 0
				break
			start[1] += 1
			if a[start[0]][start[1]] == 'E':
				flag = True
				break
			elif a[start[0]][start[1]] == '#':
				break
		elif int(j) == i[2]:
			if start[0] == 0:
				break
			start[0] -= 1
			if a[start[0]][start[1]] == 'E':
				flag = True
				break
			elif a[start[0]][start[1]] == '#':
				break
		elif int(j) == i[3]:
			if start[0] == n - 1:
				break
			start[0] += 1
			if a[start[0]][start[1]] == 'E':
				flag = True
				break
			elif a[start[0]][start[1]] == '#':
				break
	if flag:
		ans += 1
print(ans)


from itertools import permutations

def check(cmd):
	global c, field, pos
	(x, y) = (pos[0], pos[1])
	for cm in c:
		if cmd[0] == cm:
			x += 1
		elif cmd[1] == cm:
			x -= 1
		elif cmd[2] == cm:
			y -= 1
		else:
			y += 1
		if x < 0 or y < 0 or x >= n or (y >= m) or (field[x][y] == '#'):
			return False
		if field[x][y] == 'E':
			return True
p = ['0', '1', '2', '3']
(n, m) = map(int, input().split())
field = []
pos = (0, 0)
for i in range(n):
	ss = input()
	if ss.find('S') != -1:
		pos = (i, ss.find('S'))
	field.append(ss)
c = input()
answer = 0
for per in permutations(p):
	if check(per):
		answer += 1
print(answer)


(n, m) = map(int, input().split())
s = []
for i in range(0, n):
	s.append(str(input()))
inst = str(input())
sr = 0
sc = 0
for i in range(0, n):
	for j in range(0, m):
		if s[i][j] == 'S':
			sr = i
			sc = j
success = 0
for up in range(0, 4):
	for down in range(0, 4):
		if up == down:
			continue
		for left in range(0, 4):
			if left == down or left == up:
				continue
			for right in range(0, 4):
				if right == left or right == down or right == up:
					continue
				r = sr
				c = sc
				for i in range(0, len(inst)):
					ic = int(inst[i])
					if ic == up:
						r -= 1
					elif ic == down:
						r += 1
					elif ic == right:
						c += 1
					elif ic == left:
						c -= 1
					if r < 0 or c < 0 or r >= n or (c >= m):
						break
					elif s[r][c] == 'E':
						success += 1
						break
					elif s[r][c] == '#':
						break
print(success)


from itertools import permutations
(N, M) = map(int, input().split(' '))
arr = [['a'] for _ in range(N)]
for i in range(N):
	arr[i] = list(input())
	if 'S' in arr[i]:
		start = [arr[i].index('S'), i]
	if 'E' in arr[i]:
		end = [arr[i].index('E'), i]
s = input()
ans = 0
start_copy = start[:]
for pattern in permutations([[1, 0], [-1, 0], [0, 1], [0, -1]], 4):
	for num in s:
		num = int(num)
		start[0] += pattern[num][0]
		start[1] += pattern[num][1]
		if 0 > start[0] or start[0] >= M or start[1] < 0 or (start[1] >= N):
			break
		elif arr[start[1]][start[0]] == '#':
			break
		elif start[0] == end[0] and start[1] == end[1]:
			ans += 1
			break
	start = start_copy[:]
print(ans)


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)


import itertools
(n, m) = map(int, input().split())
l = []
for i in range(n):
	a = input()
	if 'S' in a:
		x = a.index('S')
		y = i
		tx = x
		ty = y
	l.append(a)
s = input()
p = list(itertools.permutations(['L', 'R', 'U', 'D']))
t = 0
for i in p:
	(x, y) = (tx, ty)
	for j in s:
		if i[int(j)] == 'L':
			if x + 1 <= m - 1 and l[y][x + 1] != '#':
				x = x + 1
				if l[y][x] == 'E':
					t += 1
					break
			else:
				break
		elif i[int(j)] == 'R':
			if x - 1 >= 0 and l[y][x - 1] != '#':
				x -= 1
				if l[y][x] == 'E':
					t += 1
					break
			else:
				break
		elif i[int(j)] == 'U':
			if y - 1 >= 0 and l[y - 1][x] != '#':
				y -= 1
				if l[y][x] == 'E':
					t += 1
					break
			else:
				break
		elif i[int(j)] == 'D':
			if y + 1 <= n - 1 and l[y + 1][x] != '#':
				y += 1
				if l[y][x] == 'E':
					t += 1
					break
			else:
				break
print(t)


def check(x, y):
	return not (x >= m or y >= n or x < 0 or (y < 0) or (flat[x][y] == '#'))
shuffles = ['0123', '0132', '0213', '0231', '0312', '0321', '1023', '1032', '1203', '1230', '1302', '1320', '2013', '2031', '2103', '2130', '2301', '2310', '3012', '3021', '3102', '3120', '3201', '3210']
(n, m) = list(map(int, input().split()))
flat = [[None] * n for __ in range(m)]
start = None
finish = None
for y in range(n):
	line = input().strip()
	for x in range(m):
		flat[x][y] = line[x]
		if flat[x][y] == 'S':
			start = (x, y)
		if flat[x][y] == 'E':
			finish = (x, y)
s = list(input().strip())
out = 0
for shuffle in shuffles:
	flag = False
	x = start[0]
	y = start[1]
	for move in s:
		if move == shuffle[0]:
			if not check(x + 1, y):
				flag = True
			x += 1
		if move == shuffle[1]:
			if not check(x - 1, y):
				flag = True
			x -= 1
		if move == shuffle[2]:
			if not check(x, y + 1):
				flag = True
			y += 1
		if move == shuffle[3]:
			if not check(x, y - 1):
				flag = True
			y -= 1
		if flag:
			break
		if x == finish[0] and y == finish[1]:
			out += 1
			break
print(out)


def check(perm):
	global sx, sy, dx, dy, m, n, instr
	x = sx
	y = sy
	for d in instr:
		dir = perm[ord(d) - ord('0')]
		x = x + dx[dir]
		y = y + dy[dir]
		if x < 0 or x >= m or y < 0 or (y >= n):
			return 0
		if s[x][y] == '#':
			return 0
		if s[x][y] == 'E':
			return 1
	return 0
(m, n) = map(int, input().split())
sx = sy = 0
ex = ey = 0
s = []
for i in range(0, m):
	s.append(input())
	for j in range(0, len(s[i])):
		if s[i][j] == 'S':
			sx = i
			sy = j
		elif s[i][j] == 'E':
			ex = i
			ey = j
instr = input()
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
ans = 0
perm = [0] * 4
for i in range(0, 4):
	for j in range(0, 4):
		for k in range(0, 4):
			for l in range(0, 4):
				if i != j and i != k and (i != l) and (j != k) and (j != l) and (k != l):
					perm[0] = i
					perm[1] = j
					perm[2] = k
					perm[3] = l
					if check(perm):
						ans = ans + 1
print(ans)


from itertools import permutations
getInputList = lambda : list(input().split())
getInputIntList = lambda : list(map(int, input().split()))
a = list(permutations(range(4)))
count = 0
(n, m) = getInputIntList()
grid = []
for i in range(n):
	grid.append(list(input()))
	if 'S' in grid[i]:
		s_pos = [i, grid[i].index('S')]
	if 'E' in grid[i]:
		e_pos = [i, grid[i].index('E')]
instruction = list(map(int, list(input())))
for i in a:
	direction = {i[0]: 'u', i[1]: 'd', i[2]: 'l', i[3]: 'r'}
	start = [s_pos[0], s_pos[1]]
	for j in instruction:
		if direction[j] == 'u':
			start[0] -= 1
		if direction[j] == 'd':
			start[0] += 1
		if direction[j] == 'l':
			start[1] -= 1
		if direction[j] == 'r':
			start[1] += 1
		if start[0] < 0 or start[1] < 0 or start[0] >= n or (start[1] >= m) or (grid[start[0]][start[1]] == '#'):
			break
		if start[0] == e_pos[0] and start[1] == e_pos[1]:
			count += 1
			break
print(count)


tt = ['1230', '1203', '1302', '1320', '1023', '1032', '2130', '2103', '2310', '2301', '2013', '2031', '3120', '3102', '3210', '3201', '3012', '3021', '0123', '0132', '0231', '0213', '0321', '0312']
(q, w) = map(int, input().split())
a = [input() for i in range(0, q)]
s = input()
for i in range(0, q):
	for j in range(0, w):
		if a[i][j] == 'S':
			(z, x) = (i, j)
			a[i] = a[i][:j] + '.' + a[i][j + 1:]
		elif a[i][j] == 'E':
			(c, v) = (i, j)
			a[i] = a[i][:j] + '.' + a[i][j + 1:]
lll = len(s)

def rr(pp, ll):
	if (pp < 0) | (ll < 0) | (pp >= q) | (ll >= w):
		return True
	return False

def f(g, h, uu, k):
	if k == lll:
		return (g == c) & (h == v)
	if (g == c) & (h == v):
		return 1
	if rr(g, h):
		return 0
	if a[g][h] != '.':
		return 0
	yyy = uu[int(s[k])]
	if yyy == '0':
		return f(g, h + 1, uu, k + 1)
	if yyy == '1':
		return f(g - 1, h, uu, k + 1)
	if yyy == '2':
		return f(g + 1, h, uu, k + 1)
	if yyy == '3':
		return f(g, h - 1, uu, k + 1)
sum = 0
for i in tt:
	sum += f(z, x, i, 0)
print(sum)


def move(s, mapp, S, E, d, n, m):
	A = S[:]
	for i in s:
		if A[0] >= n or A[0] < 0 or A[1] < 0 or (A[1] >= m):
			return False
		if A == E:
			return True
		if d[A[0]][A[1]] == '#':
			return False
		if mapp[i] == 'l':
			A[1] -= 1
		elif mapp[i] == 'r':
			A[1] += 1
		elif mapp[i] == 'u':
			A[0] -= 1
		elif mapp[i] == 'd':
			A[0] += 1
	if A == E:
		return True
	return False
(n, m) = map(int, input().split())
d = [list(input()) for i in range(n)]
s = list(input())
for i in range(n):
	if 'S' in d[i]:
		x = i
		y = d[i].index('S')
	if 'E' in d[i]:
		x1 = i
		y1 = d[i].index('E')
S = [x, y]
E = [x1, y1]
mapp = {'0': 'd', '1': 'l', '2': 'u', '3': 'r'}
c = 0
for q in range(4):
	for w in range(4):
		if w != q:
			for e in range(4):
				if e != w and e != q:
					for r in range(4):
						if r != e and r != w and (r != q):
							(q1, w1, e1, r1) = map(str, [q, w, e, r])
							mapp[q1] = 'l'
							mapp[w1] = 'r'
							mapp[e1] = 'u'
							mapp[r1] = 'd'
							if move(s, mapp, S, E, d, n, m):
								c += 1
print(c)


import itertools
dic = {'U': (0, 1), 'R': (1, 0), 'D': (0, -1), 'L': (-1, 0)}
(h, w) = map(int, input().split())
field = [[''] * w for _ in range(h)]
for i in range(h):
	a = list(input())
	field[i] = a
s = input()
(sx, sy, ex, ey) = (0, 0, 0, 0)
for i in range(h):
	for j in range(w):
		if field[i][j] == 'S':
			(sx, sy) = (i, j)
		elif field[i][j] == 'E':
			(ex, ey) = (i, j)
seq = ('U', 'R', 'D', 'L')
rec = {}
ans = 0
for k in itertools.permutations(seq):
	rec = {}
	for i in range(4):
		rec[i] = k[i]
	(x, y) = (sx, sy)
	for j in range(len(s)):
		c = int(s[j])
		(x, y) = (x + dic[rec[c]][0], y + dic[rec[c]][1])
		if x == ex and y == ey:
			ans += 1
			break
		elif 0 <= x < h and 0 <= y < w and (field[x][y] != '#'):
			continue
		else:
			break
print(ans)


import sys, itertools

def getNextIdx(x, y, d):
	move = {'U': (-1, 0), 'D': (1, 0), 'R': (0, 1), 'L': (0, -1)}
	return (x + move[d][0], y + move[d][1])

def tryComb(comb, sol, sx, sy, ex, ey):
	for i in sol:
		(sx, sy) = getNextIdx(sx, sy, comb[int(i)])
		if sx == ex and sy == ey:
			return 1
		if sx < 0 or sy < 0 or sx >= n or (sy >= m):
			return 0
		if data[sx][sy] == '#':
			return 0
	return 0
data = []
count = 0
(n, m) = map(int, sys.stdin.readline().rstrip().split())
for i in range(n):
	data.append(sys.stdin.readline().rstrip())
sol = sys.stdin.readline().rstrip()
for x in range(n):
	for y in range(m):
		if data[x][y] == 'S':
			(sx, sy) = (x, y)
		if data[x][y] == 'E':
			(ex, ey) = (x, y)
for comb in itertools.permutations(['U', 'D', 'R', 'L']):
	if tryComb(comb, sol, sx, sy, ex, ey):
		count += 1
print(count)


def coo(a, b):
	if b == 'U':
		return [a[0] - 1, a[1]]
	elif b == 'L':
		return [a[0], a[1] - 1]
	elif b == 'R':
		return [a[0], a[1] + 1]
	elif b == 'D':
		return [a[0] + 1, a[1]]

def val(c, n, m):
	if 0 <= c[0] < n and 0 <= c[1] < m:
		return True
	return False

def eva(data, inst, dim, start, n, m):
	nex = start
	for i in inst:
		nex = coo(nex, dim[int(i)])
		if val(nex, n, m):
			res = data[nex[0]][nex[1]]
			if res == 'E':
				return 1
			elif res == '#':
				return 0
		else:
			return 0
	return 0
from itertools import *
(n, m) = list(map(int, input().split()))
data = []
start = [0, 0]
for i in range(n):
	d = input()
	for j in range(m):
		if d[j] == 'S':
			start = [i, j]
	data.append(d)
inst = input()
pos = permutations('ULRD')
count = 0
for dim in pos:
	count += eva(data, inst, dim, start, n, m)
print(count)


(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
	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'])):
	i += road(list(x))
print(i)


import itertools
inf = float('inf')
read_ints = lambda : list(map(int, input().split()))

def findS(maze, n, m):
	for i in range(n):
		for j in range(m):
			if maze[i][j] == 'S':
				return (i, j)

def f(maze, n, m, si, sj, dirs, path):
	(i, j) = (si, sj)
	for p in path:
		i += dirs[p][0]
		j += dirs[p][1]
		if not (0 <= i < n and 0 <= j < m):
			return False
		if maze[i][j] == 'E':
			return True
		if maze[i][j] == '#':
			return False
	return False
(n, m) = read_ints()
maze = [input() for _ in range(n)]
path = [int(c) for c in input()]
(si, sj) = findS(maze, n, m)
dirs = [(0, 0) for _ in range(4)]
cnt = 0
for ds in itertools.permutations(range(4)):
	for (d, move) in zip(ds, [(0, 1), (0, -1), (1, 0), (-1, 0)]):
		dirs[d] = move
	if f(maze, n, m, si, sj, dirs, path):
		cnt += 1
print(cnt)


class Point:

	def __init__(self, i, j):
		self.i = i
		self.j = j

	def pp(self):
		print('%d %d' % (self.i, self.j))

	def move(self, p):
		return Point(self.i + p.i, self.j + p.j)

	def pos(self, p):
		return self.i == p.i and self.j == p.j

	def out(self):
		return self.i < 0 or self.i == n or self.j < 0 or (self.j == m)
(n, m) = map(int, input().split())
obs = []
for i in range(n):
	stmp = str(input())
	if 'S' in stmp:
		start = Point(i, stmp.find('S'))
	if 'E' in stmp:
		end = Point(i, stmp.find('E'))
	for j in range(m):
		if stmp[j] == '#':
			obs.append(Point(i, j))
drt = str(input())
cnt = 0
up = Point(1, 0)
down = Point(-1, 0)
right = Point(0, 1)
left = Point(0, -1)
for u in range(4):
	for d in range(4):
		if d == u:
			continue
		for r in range(4):
			if r == u or r == d:
				continue
			for l in range(4):
				if l == u or l == d or l == r:
					continue
				cur = start
				for s in drt:
					if int(s) == u:
						cur = cur.move(up)
					elif int(s) == d:
						cur = cur.move(down)
					elif int(s) == r:
						cur = cur.move(right)
					elif int(s) == l:
						cur = cur.move(left)
					if any((cur.pos(x) for x in obs)) or cur.out():
						break
					if cur.pos(end):
						cnt += 1
						break
print(cnt)


import itertools
start = [-1, -1]
(ymax, xmax) = [int(i) for i in input().split(' ')]
maze = [[]] * ymax
for y in range(ymax):
	maze[y] = input()
	try:
		start = [maze[y].index('S'), y]
	except:
		pass
path = [int(d) for d in input()]
count = 0
for mapping in list(itertools.permutations([(0, 1), (0, -1), (1, 0), (-1, 0)])):
	(x, y) = start
	for p in path:
		x += mapping[p][0]
		y += mapping[p][1]
		if x < 0 or x >= xmax or y < 0 or (y >= ymax) or (maze[y][x] == '#'):
			break
		if maze[y][x] == 'E':
			count += 1
			break
print(count)


def judge():
	(x, y) = (stx, sty)
	for ch in s:
		u = ord(ch) - ord('0')
		x += loca[u][0]
		y += loca[u][1]
		if x < 0 or x >= n or y < 0 or (y >= m) or (tu[x][y] == '#'):
			return False
		if tu[x][y] == 'E':
			return True
	return False
R = lambda : map(int, input().split())
(n, m) = R()
tu = tuple((input() for _ in range(n)))
for i in range(n):
	for j in range(m):
		if tu[i][j] == 'S':
			(stx, sty) = (i, j)
(s, ans) = (input(), 0)
from itertools import permutations
for loca in permutations([(0, -1), (0, 1), (-1, 0), (1, 0)], 4):
	if judge():
		ans += 1
print(ans)


(n, m) = map(int, input().split())
matrix = [list(input()) for i in range(n)]
line = list(input())
s = [0, 0]
for i in range(n):
	out = False
	for j in range(m):
		if matrix[i][j] == 'S':
			s = [i, j]
			out = True
			break
	if out:
		break
steps = [(-1, 0), (0, -1), (1, 0), (0, 1)]
counter = 0
for el1 in steps:
	for el2 in steps:
		for el3 in steps:
			for el4 in steps:
				se = {el1, el2, el3, el4}
				if len(se) != 4:
					continue
				ma = {'0': el1, '1': el2, '2': el3, '3': el4}
				current_x = s[0]
				current_y = s[1]
				for el in line:
					current_x += ma[el][0]
					current_y += ma[el][1]
					if 0 <= current_x < n and 0 <= current_y < m:
						if matrix[current_x][current_y] == '#':
							break
						if matrix[current_x][current_y] == 'E':
							counter += 1
							break
					else:
						break
print(counter)


import itertools
d = [[-1, 0], [1, 0], [0, -1], [0, 1]]
(n, m) = map(int, input().split())
(g, si, sj) = ([input() for i in range(n)], -1, -1)
for (i, gi) in enumerate(g):
	if 'S' in gi:
		(si, sj) = (i, gi.find('S'))
s = input()

def f(p):
	(i, j) = (si, sj)
	for x in s:
		di = p[int(x)]
		(i, j) = (i + d[di][0], j + d[di][1])
		if i < 0 or i >= n or j < 0 or (j >= m) or (g[i][j] == '#'):
			return 0
		elif g[i][j] == 'E':
			return 1
	return 0
print(sum((f(p) for p in itertools.permutations([0, 1, 2, 3]))))


import sys

def data_input():
	mazedim = tuple(map(int, sys.stdin.readline().strip().split()))
	maze = []
	for r in range(mazedim[0]):
		line = sys.stdin.readline()
		maze.append(line.strip())
		if 'S' in line:
			starting_point = (r, line.index('S'))
		if 'E' in line:
			end_point = (r, line.index('E'))
	instruction = [int(x) for x in sys.stdin.readline().strip()]
	return (maze, mazedim, instruction, starting_point, end_point)

def direction():
	direc = list('UDLR')
	direc_possible = []
	c = [0 for _ in range(len(direc))]
	direc_possible.append(direc[:])
	i = 0
	while i < len(direc):
		if c[i] < i:
			if i % 2 == 0:
				(direc[0], direc[i]) = (direc[i], direc[0])
			else:
				(direc[c[i]], direc[i]) = (direc[i], direc[c[i]])
			direc_possible.append(direc[:])
			c[i] += 1
			i = 0
		else:
			c[i] = 0
			i += 1
	return direc_possible

def move(ins, x, y):
	if ins == 'U':
		return (x - 1, y)
	if ins == 'D':
		return (x + 1, y)
	if ins == 'L':
		return (x, y - 1)
	if ins == 'R':
		return (x, y + 1)

def solve(m, mdim, inst, st, end):
	directions = direction()
	counter = 0
	for d in directions:
		curpos = st
		for ins in inst:
			curpos = move(d[ins], *curpos)
			if curpos[0] < 0 or curpos[0] >= mdim[0]:
				break
			if curpos[1] < 0 or curpos[1] >= mdim[1]:
				break
			if m[curpos[0]][curpos[1]] == '#':
				break
			if curpos == end:
				counter += 1
				break
	return counter
print(solve(*data_input()))


from itertools import permutations
(n, m) = list(map(int, input().split()))
a = []
for i in range(n):
	a.append(input())
s = input()
b = [[1, 0], [0, 1], [-1, 0], [0, -1]]
ans = 0

def f(s, l, n, m):
	temp = 0
	for i in range(n):
		for j in range(m):
			if a[i][j] == 'S':
				p = [i, j]
				temp = 1
				break
		if temp:
			break
	for i in s:
		p[0] += l[int(i) - 1][0]
		p[1] += l[int(i) - 1][1]
		if p[0] < 0 or p[0] >= n:
			return 0
		if p[1] < 0 or p[1] >= m:
			return 0
		if a[p[0]][p[1]] == '#':
			return 0
		if a[p[0]][p[1]] == 'E':
			return 1
	return 0
for i in permutations(b):
	ans += f(s, list(i), n, m)
print(ans)


from itertools import permutations
dirs = 'UDLR'
perms = [''.join(p) for p in permutations(dirs)]
change = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}
(n, m) = list(map(int, input().split()))
grid = []
for _ in range(n):
	grid.append(list(input().rstrip()))
ins = list(map(int, list(input().rstrip())))
for i in range(n):
	for j in range(m):
		if grid[i][j] == 'S':
			start = (i, j)
		elif grid[i][j] == 'E':
			end = (i, j)
ans = 0
for p in perms:
	curr = start
	for i in ins:
		d = change[p[i]]
		nxt = (curr[0] + d[0], curr[1] + d[1])
		if nxt[0] < 0 or nxt[0] >= n or nxt[1] < 0 or (nxt[1] >= m) or (grid[nxt[0]][nxt[1]] == '#'):
			break
		elif nxt == end:
			ans += 1
			break
		else:
			curr = nxt
print(ans)


(n, m) = map(int, input().split())
k = [[] * m for i in range(n)]
for i in range(n):
	k[i] = input()
	if 'S' in k[i]:
		y = k[i].index('S')
		x = i
	if 'E' in k[i]:
		y1 = k[i].index('E')
		x1 = i
s = input()
schet = 0
j = 'dlur'
c = 0
for i in j:
	u = j[:]
	u = u.replace(i, '')
	for o in u:
		t = u[:]
		t = t.replace(o, '')
		for q in t:
			g = t[:]
			g = g.replace(q, '')
			l = {'0': i, '1': o, '2': q, '3': g}
			lookx = x
			looky = y
			c += 1
			for w in s:
				if l[w] == 'd':
					lookx += 1
					if lookx >= n:
						break
				elif l[w] == 'l':
					looky -= 1
					if looky < 0:
						break
				elif l[w] == 'r':
					looky += 1
					if looky >= m:
						break
				elif l[w] == 'u':
					lookx -= 1
					if lookx < 0:
						break
				if k[lookx][looky] == '#':
					break
				if looky == y1 and lookx == x1:
					schet += 1
					break
print(schet)


import itertools
dirs = list(itertools.permutations(['r', 'l', 'd', 'u']))
(n, m) = 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

def check_valid(maze, dirs, robot, mapping):
	(i, j) = robot
	if maze[i][j] is 'E':
		return True
	if len(dirs) == 0:
		return False
	c = int(dirs[0])
	if mapping[c] is 'u':
		if i == 0:
			return False
		if maze[i - 1][j] is '#':
			return False
		return check_valid(maze, dirs[1:], (i - 1, j), mapping)
	if mapping[c] is 'd':
		if i == len(maze) - 1:
			return False
		if maze[i + 1][j] is '#':
			return False
		return check_valid(maze, dirs[1:], (i + 1, j), mapping)
	if mapping[c] is 'r':
		if j == len(maze[0]) - 1:
			return False
		if maze[i][j + 1] is '#':
			return False
		return check_valid(maze, dirs[1:], (i, j + 1), mapping)
	if mapping[c] is 'l':
		if j == 0:
			return False
		if maze[i][j - 1] is '#':
			return False
		return check_valid(maze, dirs[1:], (i, j - 1), mapping)
	return True
s = str(input())
(n, m) = (int(s.split(' ')[0]), int(s.split(' ')[1]))
maze = []
for i in range(n):
	s = str(input())
	if 'S' in s:
		robot = (i, s.find('S'))
	maze.append(s)
dirs = input()
ct = 0
for mapping in list(itertools.permutations(['u', 'd', 'l', 'r'])):
	if check_valid(maze, dirs, robot, mapping):
		ct = ct + 1
print(ct)


(n, m) = map(int, input().split())
lab = [input() for i in range(n)]
s = input()
for i in range(n):
	for j in range(m):
		if lab[i][j] == 'S':
			start = (i, j)
		elif lab[i][j] == 'E':
			finish = (i, j)
S = {0, 1, 2, 3}
perm = list()
for U in S:
	for D in S - {U}:
		for L in S - ({U} | {D}):
			for R in S - ({U} | {D} | {L}):
				perm.append((U, D, L, R))
count = 0
for (U, D, L, R) in perm:
	(X, Y) = start
	for (i, el) in enumerate(s):
		el = int(el)
		if el == U:
			X -= 1
			if X < 0 or lab[X][Y] == '#':
				break
		elif el == D:
			X += 1
			if X == n or lab[X][Y] == '#':
				break
		elif el == L:
			Y -= 1
			if Y < 0 or lab[X][Y] == '#':
				break
		elif el == R:
			Y += 1
			if Y == m or lab[X][Y] == '#':
				break
		if (X, Y) == finish:
			count += 1
			break
print(count)


(N, M) = map(int, input().split())
arr = [[] for i in range(N)]
start = [-1, -1]
for i in range(N):
	s = input()
	for j in range(M):
		arr[i].append(s[j])
		if s[j] == 'S':
			start = [i, j]
s = input()
v = [0, 1]
n = [0, -1]
p = [1, 0]
l = [-1, 0]
d = [[v, n, p, l], [v, n, l, p], [v, p, n, l], [v, p, l, n], [v, l, p, n], [v, l, n, p], [n, v, p, l], [n, v, l, p], [n, p, l, v], [n, p, v, l], [n, l, v, p], [n, l, p, v], [p, n, v, l], [p, n, l, v], [p, v, n, l], [p, v, l, n], [p, l, v, n], [p, l, n, v], [l, v, p, n], [l, v, n, p], [l, p, n, v], [l, p, v, n], [l, n, v, p], [l, n, p, v]]
ans = 0
for ver in d:
	NO = ver[0]
	OD = ver[1]
	DV = ver[2]
	TR = ver[3]
	cur = [-1, -1]
	cur[0] = int(start[0])
	cur[1] = int(start[1])
	fl = -1
	for i in s:
		i = int(i)
		if i == 0:
			cur[0] += NO[0]
			cur[1] += NO[1]
		elif i == 1:
			cur[0] += OD[0]
			cur[1] += OD[1]
		elif i == 2:
			cur[0] += DV[0]
			cur[1] += DV[1]
		else:
			cur[0] += TR[0]
			cur[1] += TR[1]
		if cur[0] < 0 or cur[1] < 0 or cur[1] >= M or (cur[0] >= N):
			fl = 0
			break
		if arr[cur[0]][cur[1]] == '#':
			fl = -2
			break
		if arr[cur[0]][cur[1]] == 'E':
			fl = 1
			break
	if fl == 1:
		ans += 1
print(ans)


from itertools import permutations
(n, m) = map(int, input().split())

def in_map(x, y):
	return 0 <= x < n and 0 <= y < m
maze = []
for _ in range(n):
	maze.append(input())
s = [int(x) for x in list(input())]
for i in range(n):
	for j in range(m):
		if maze[i][j] == 'S':
			s_r = (i, j)
ans = 0
for asdf in permutations('LDUR', 4):
	valid = True
	(x, y) = s_r
	for i in range(len(s)):
		if asdf[s[i]] == 'L':
			y -= 1
		elif asdf[s[i]] == 'R':
			y += 1
		elif asdf[s[i]] == 'D':
			x += 1
		elif asdf[s[i]] == 'U':
			x -= 1
		if not in_map(x, y):
			valid = False
		elif maze[x][y] == '#':
			valid = False
		elif maze[x][y] == 'E':
			break
	if in_map(x, y):
		if maze[x][y] != 'E':
			valid = False
	if valid:
		ans += 1
print(ans)


from itertools import permutations

def main():
	(n, m) = map(int, input().split())
	maze = []
	for y in range(n):
		row = [True] * m
		maze.append(row)
		for (x, c) in enumerate(input()):
			if c == '#':
				row[x] = False
			elif c == 'S':
				s = (y, x)
			elif c == 'E':
				e = (y, x)
	(cmd, r) = (list(map(int, input())), 0)
	for abc in permutations(((-1, 0), (1, 0), (0, -1), (0, 1))):
		(y, x) = s
		for (dy, dx) in map(abc.__getitem__, cmd):
			y += dy
			x += dx
			if not (n > y >= 0 <= x < m and maze[y][x]):
				break
			elif (y, x) == e:
				r += 1
				break
	print(r)
main()


def STR():
	return list(input())

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST():
	return list(map(int, input().split()))

def STRING():
	return input()
from heapq import heappop, heappush
from bisect import *
from collections import deque
from math import *
from itertools import permutations
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

def valid(i, j):
	if i >= 0 and i <= n - 1 and (j >= 0) and (j <= m - 1):
		return True
	return False
(n, m) = MAP()
g = []
for i in range(n):
	g.append(STRING())
s = STRING()
(s1, s2) = (0, 0)
(e1, e2) = (0, 0)
f = 0
for i in range(n):
	for j in range(m):
		if g[i][j] == 'S':
			s1 = i
			s2 = j
			f = 1
			break
		if f == 1:
			break
start = (s1, s2)
f = 0
for i in range(n):
	for j in range(m):
		if g[i][j] == 'E':
			e1 = i
			e2 = j
			f = 1
			break
		if f == 1:
			break
end = (e1, e2)
mapping = ((0, -1), (0, 1), (-1, 0), (1, 0))
cnt = 0
for i in permutations(mapping, 4):
	now = start
	for j in s:
		k = i[int(j)]
		x = now[0] + k[0]
		y = now[1] + k[1]
		if valid(x, y) == False:
			break
		now = (x, y)
		if now == end:
			cnt += 1
			break
		elif g[x][y] == '#':
			break
print(cnt)


(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]):
	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
import sys
moves = list(itertools.permutations([(0, 1), (1, 0), (-1, 0), (0, -1)]))

def get_s(g):
	for i in range(len(g)):
		for j in range(len(g[i])):
			if g[i][j] == 'S':
				return (i, j)

def crash(g, p):
	return ((p[0] < 0 or p[0] >= len(g)) or (p[1] < 0 or p[1] >= len(g[0]))) or g[p[0]][p[1]] in '#'

def go(g, ms, ps):
	s = get_s(g)
	for a in ms:
		s = (s[0] + ps[a][0], s[1] + ps[a][1])
		if crash(g, s):
			return False
		if g[s[0]][s[1]] == 'E':
			return True
	return False
lines = [i for i in sys.stdin][1:]
(g, ms) = ([s.strip() for s in lines[:-1]], [int(k) for k in lines[-1].strip()])
print(sum(map(lambda x: go(g, ms, x), moves)))


(n, m) = map(int, input().split())
maze = []
start = None
end = None
for i in range(n):
	line = input()
	s_index = line.find('S')
	if s_index != -1:
		start = (i, s_index)
	e_index = line.find('E')
	if e_index != -1:
		end = (i, e_index)
	maze.append(line)
inp = input()
move_list = []
for c in inp:
	move_list.append(int(c))
dir_list = [(-1, 0), (0, -1), (1, 0), (0, 1)]
import itertools
dir_list_p = list(itertools.permutations(dir_list))
count = 0
for dir_lookup in dir_list_p:
	current = start
	for move in move_list:
		move = dir_lookup[move]
		(r, c) = (current[0] + move[0], current[1] + move[1])
		if r < 0 or c < 0 or r >= n or (c >= m):
			break
		if maze[r][c] == '#':
			break
		if maze[r][c] == 'E':
			count += 1
			break
		current = (r, c)
print(count)


def check(a, b, c, d):
	dx = {a: 1, b: 0, c: -1, d: 0}
	dy = {a: 0, b: 1, c: 0, d: -1}
	x = startx
	y = starty
	for i in direction:
		x += dx[i]
		y += dy[i]
		if 0 <= x < n and 0 <= y < m:
			if map[x][y] == '#':
				return False
			if map[x][y] == 'E':
				return True
			continue
		else:
			return False
	return False
(n, m) = map(int, input().split())
map = []
for i in range(n):
	map.append(list(input()))
	if 'S' in map[i]:
		startx = i
		starty = map[i].index('S')
direction = [int(i) for i in list(input())]
ans = 0
for i in range(4):
	for j in range(4):
		if i != j:
			for k in range(4):
				if i != k and k != j:
					for l in range(4):
						if l != i and l != j and (l != k):
							if check(i, j, k, l):
								ans += 1
print(ans)


def Diff(li1, li2):
	li_dif = [i for i in li1 + li2 if i not in li1 or i not in li2]
	return li_dif
(n, m) = list(map(int, input().split()))
g = []
for i in range(n):
	g.append(input())
p = input()
(x, y, f) = (0, 0, 0)
for i in range(n):
	for j in range(m):
		if g[i][j] == 'S':
			(x, y) = (i, j)
			f = 1
			break
	if f:
		break
ans = 0
d = {}
l = ['l', 'r', 'u', 'd']
for i in l:
	d['0'] = i
	l1 = Diff(l, [i])
	for j in l1:
		d['1'] = j
		l2 = Diff(l, [i, j])
		for k in l2:
			d['2'] = k
			l3 = Diff(l, [i, j, k])
			for t in l3:
				d['3'] = t
				f = 0
				(a, b) = (x, y)
				for pt in p:
					if d[pt] == 'l':
						a = a - 1
					elif d[pt] == 'r':
						a = a + 1
					elif d[pt] == 'u':
						b = b + 1
					elif d[pt] == 'd':
						b = b - 1
					if a < 0 or a >= n or b < 0 or (b >= m):
						break
					elif g[a][b] == '#':
						break
					elif g[a][b] == 'E':
						f = 1
						break
				if f:
					ans = ans + 1
print(ans)


(n, m) = map(int, input().split())
l = [input() for i in range(n)]
s = input()
st = []
finish = []
for i in range(n):
	if l[i].find('S') != -1:
		st = [i, l[i].find('S')]
	if l[i].find('E') != -1:
		finish = [i, l[i].find('E')]

def per(a):
	if len(a) == 0:
		return [[]]
	else:
		res = []
		for i in range(len(a)):
			x = a[i]
			a.pop(i)
			for y in per(a):
				res += [[x] + y]
			a.insert(i, x)
		return res
move = per([0, 1, 2, 3])
ans = 0
for x in move:
	L = x[0]
	R = x[1]
	U = x[2]
	D = x[3]
	ok = True
	start = [st[i] for i in range(2)]
	for i in range(len(s)):
		k = int(s[i])
		if k == L:
			start[1] -= 1
		elif k == R:
			start[1] += 1
		elif k == U:
			start[0] -= 1
		else:
			start[0] += 1
		if start[0] < 0 or start[0] >= n or start[1] < 0 or (start[1] >= m) or (l[start[0]][start[1]] == '#'):
			ok = False
			break
		elif l[start[0]][start[1]] == 'E':
			break
	if ok and start == finish:
		ans += 1
print(ans)


def translate(perm, num):
	for i in range(len(perm)):
		if perm[i] == num:
			return i
import itertools
inp = input().split(' ')
h = int(inp[0])
w = int(inp[1])
maze = [[0 for x in range(w)] for y in range(h)]
startx = -1
starty = -1
for k in range(h):
	inp = input()
	for i in range(w):
		maze[k][i] = inp[i]
		if inp[i] == 'S':
			startx = i
			starty = k
inp = input()
possible = list(itertools.permutations(['0', '1', '2', '3']))
res = 0
for i in range(len(possible)):
	currx = startx
	curry = starty
	perm = possible[i]
	for k in range(len(inp)):
		if translate(perm, inp[k]) == 0:
			currx = currx - 1
		elif translate(perm, inp[k]) == 1:
			curry = curry + 1
		elif translate(perm, inp[k]) == 2:
			currx = currx + 1
		elif translate(perm, inp[k]) == 3:
			curry = curry - 1
		if curry < 0 or curry >= h or currx < 0 or (currx >= w):
			break
		elif maze[curry][currx] == '#':
			break
		elif maze[curry][currx] == 'E':
			res = res + 1
			break
print(res)


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
(n, m) = map(int, input().split())
g = [list(input().strip()) for _ in range(n)]
ins = list(map(int, input().strip()))
(sx, sy) = (-1, -1)
for i in range(n):
	for j in range(m):
		if g[i][j] == 'S':
			(sx, sy) = (i, j)
maps = [dict([(i, x[i]) for i in range(4)]) for x in permutations([0, 1, 2, 3])]
res = 0
for mp in maps:
	(rx, ry) = (sx, sy)
	good = True
	for i in ins:
		if mp[i] == 0:
			rx += 1
		elif mp[i] == 1:
			rx -= 1
		elif mp[i] == 2:
			ry += 1
		elif mp[i] == 3:
			ry -= 1
		if not 0 <= rx < n:
			good = False
			break
		if not 0 <= ry < m:
			good = False
			break
		if g[rx][ry] == '#':
			good = False
			break
		if g[rx][ry] == 'E':
			break
	try:
		if g[rx][ry] == 'E':
			res += good
	except:
		continue
print(res)


import itertools as it

def f1(x, y):
	return (x + 1, y)

def f2(x, y):
	return (x - 1, y)

def f3(x, y):
	return (x, y + 1)

def f4(x, y):
	return (x, y - 1)
d = [f1, f2, f3, f4]
(n, m) = list(map(int, input().split()))
ls = []
ls.append('#' * (m + 2))
for i in range(n):
	ls.append('#' + input() + '#')
	if 'S' in ls[-1]:
		start = (i + 1, ls[-1].index('S'))
ls.append(ls[0])
mov = input()
count = 0
for perm in it.permutations(d):
	found = False
	current = start
	for c in mov:
		new_pos = perm[int(c)](*current)
		if ls[new_pos[0]][new_pos[1]] == '#':
			break
		elif ls[new_pos[0]][new_pos[1]] == 'E':
			found = True
			break
		else:
			current = new_pos
	if found:
		count += 1
print(count)


from itertools import permutations
(n, m) = map(int, input().split())
maze = [list(input()) for _ in range(n)]
s = list(map(int, list(input())))
dxy = [(1, 0), (0, 1), (-1, 0), (0, -1)]
sx = sy = ex = ey = 0
for y in range(n):
	for x in range(m):
		if maze[y][x] == 'S':
			sx = x
			sy = y
		elif maze[y][x] == 'E':
			ex = x
			ey = y
ans = 0
for p in permutations(range(4)):
	x = sx
	y = sy
	for i in s:
		x += dxy[p[i]][0]
		y += dxy[p[i]][1]
		if x == ex and y == ey:
			ans += 1
			break
		elif x == -1 or x == m or y == -1 or (y == n) or (maze[y][x] == '#'):
			break
print(ans)


(m, n) = map(int, input().split())
arr = []
num = 0
for i in range(m):
	a = input()
	if 'S' in a:
		xs = a.index('S')
		ys = i
	if 'E' in a:
		xe = a.index('E')
		ye = i
	arr.append(a)
direct = [[1, 0], [-1, 0], [0, 1], [0, -1]]
nums = [int(i) for i in input()]
for i in direct:
	di = direct.index(i)
	direct1 = direct[:di] + direct[di + 1:]
	for j in direct1:
		dj = direct1.index(j)
		direct2 = direct1[:dj] + direct1[dj + 1:]
		for k in direct2:
			dk = direct2.index(k)
			direct3 = direct2[:dk] + direct2[dk + 1:]
			l = direct3[0]
			numDict = {0: i, 1: j, 2: l, 3: k}
			(x1, y1) = (xs, ys)
			for z in nums:
				p = numDict[z]
				(x1, y1) = (x1 + p[0], y1 + p[1])
				if -1 < x1 < n and -1 < y1 < m:
					a = arr[y1][x1]
					if a == 'E':
						num += 1
						break
					elif a == '#':
						break
				else:
					break
print(num)


from itertools import permutations

def convert(v):
	s = ''
	for i in v:
		if i == [-1, 0]:
			s += 'U'
		elif i == [1, 0]:
			s += 'D'
		elif i == [0, -1]:
			s += 'L'
		else:
			s += 'R'
	return s
lab = []
begin = [0, 0]
end = [0, 0]
ans = 0
(n, m) = map(int, input().split())
for i in range(n):
	lab.append([])
	now = input()
	for j in range(m):
		if now[j] == 'S':
			begin = [i, j]
		if now[j] == 'E':
			end = [i, j]
		if now[j] == '#':
			lab[-1].append(False)
		else:
			lab[-1].append(True)
cmd = input()
vectors = [[0, 1], [0, -1], [1, 0], [-1, 0]]
for v in permutations(vectors):
	pos = begin + []
	good = True
	for i in cmd:
		pos[0] += v[int(i)][0]
		pos[1] += v[int(i)][1]
		if not (0 <= pos[0] < n and 0 <= pos[1] < m) or not lab[pos[0]][pos[1]]:
			good = False
			break
		elif pos == end:
			break
	if good and pos == end:
		ans += 1
print(ans)


from itertools import permutations
perm = permutations(['L', 'R', 'U', 'D'])
d = []
for i in perm:
	d.append(i)
(n, m) = map(int, input().split())
a = []
sco = []
eco = []
for i in range(n):
	a.append(list(input()))
	if 'S' in a[i]:
		sco.append(i)
		sco.append(a[i].index('S'))
	if 'E' in a[i]:
		eco.append(i)
		eco.append(a[i].index('E'))
b = list(map(int, list(input())))
c = []
for i in range(24):
	ref = d[i]
	(x1, y1) = (sco[0], sco[1])
	(x2, y2) = (eco[0], eco[1])
	for j in b:
		try:
			if ref[j] == 'U':
				x1 -= 1
				if x1 < 0 or y1 < 0:
					c.append(False)
					break
				elif a[x1][y1] == '#':
					c.append(False)
					break
				elif a[x1][y1] == 'E':
					c.append(True)
					break
				elif a[x1][y1] == '.':
					continue
			elif ref[j] == 'D':
				x1 += 1
				if x1 < 0 or y1 < 0:
					c.append(False)
					break
				elif a[x1][y1] == '#':
					c.append(False)
					break
				elif a[x1][y1] == 'E':
					c.append(True)
					break
				elif a[x1][y1] == '.':
					continue
			elif ref[j] == 'L':
				y1 -= 1
				if x1 < 0 or y1 < 0:
					c.append(False)
					break
				elif a[x1][y1] == '#':
					c.append(False)
					break
				elif a[x1][y1] == 'E':
					c.append(True)
					break
				elif a[x1][y1] == '.':
					continue
			elif ref[j] == 'R':
				y1 += 1
				if x1 < 0 or y1 < 0:
					c.append(False)
					break
				elif a[x1][y1] == '#':
					c.append(False)
					break
				elif a[x1][y1] == 'E':
					c.append(True)
					break
				elif a[x1][y1] == '.':
					continue
		except:
			c.append(False)
			break
print(c.count(True))


import itertools
(n, m) = tuple(map(int, input().split()))
maze = []
for _ in range(n):
	maze.append(list(input()))
instructions = input()
start_position = (-1, -1)
end_position = (-1, -1)
for i in range(n):
	for j in range(m):
		if maze[i][j] == 'S':
			start_position = (i, j)
		elif maze[i][j] == 'E':
			end_position = (i, j)

def solveMazeWithMapping(U, D, L, R):
	current_position = list(start_position)
	for number in instructions:
		number = int(number)
		(i, j) = (current_position[0], current_position[1])
		if number == U:
			if i > 0 and maze[i - 1][j] != '#':
				current_position[0] -= 1
			else:
				return False
		elif number == D:
			if i < n - 1 and maze[i + 1][j] != '#':
				current_position[0] += 1
			else:
				return False
		elif number == L:
			if j > 0 and maze[i][j - 1] != '#':
				current_position[1] -= 1
			else:
				return False
		elif j < m - 1 and maze[i][j + 1] != '#':
			current_position[1] += 1
		else:
			return False
		if tuple(current_position) == end_position:
			return True
answer = 0
mappings = list(itertools.permutations([0, 1, 2, 3]))
for mp in mappings:
	if solveMazeWithMapping(mp[0], mp[1], mp[2], mp[3]):
		answer += 1
print(answer)


def goField(field, rule, dirs, start):
	pos = start
	for i in rule:
		i = int(i)
		if dirs[i] == 0:
			pos[0] -= 1
		if dirs[i] == 1:
			pos[1] += 1
		if dirs[i] == 2:
			pos[0] += 1
		if dirs[i] == 3:
			pos[1] -= 1
		if pos[0] < 0 or pos[1] < 0 or pos[0] >= len(field) or (pos[1] >= len(field[0])) or (field[pos[0]][pos[1]] == '#'):
			return 0
		if field[pos[0]][pos[1]] == 'E':
			return 1
	return 0

def main():
	import itertools
	(n, m) = [int(i) for i in input().split()]
	field = []
	start = [0, 0]
	for i in range(n):
		s = input()
		field.append(s)
		if 'S' in s:
			start = [i, s.index('S')]
	rule = input()
	dirs = [0, 1, 2, 3]
	amount = 0
	for dir in list(itertools.permutations(dirs)):
		amount += goField(field, rule, dir, start.copy())
	print(amount)
main()


(n, m) = 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)


(n, m) = map(int, input().split())
data = [[] for up in range(n)]
start = []
end = []
for i in range(n):
	data[i] = input()
	if 'S' in data[i]:
		start.append(i)
		start.append(data[i].find('S'))
	if 'E' in data[i]:
		end.append(i)
		end.append(data[i].find('E'))
save = start.copy()
ans = 0
s = input()
for up in range(4):
	for down in range(4):
		if down != up:
			for left in range(4):
				if left != up and left != down:
					for right in range(4):
						if right != up and right != down and (right != left):
							start = save.copy()
							for i in range(len(s)):
								if int(s[i]) == up:
									start[0] -= 1
								if int(s[i]) == down:
									start[0] += 1
								if int(s[i]) == left:
									start[1] -= 1
								if int(s[i]) == right:
									start[1] += 1
								if start[0] < 0 or start[0] >= n or start[1] < 0 or (start[1] >= m) or (data[start[0]][start[1]] == '#'):
									break
								if start[0] == end[0] and start[1] == end[1]:
									ans += 1
									break
print(ans)


import itertools
mov = {'U': [0, -1], 'D': [0, 1], 'L': [-1, 0], 'R': [1, 0]}

def is_valid(x, y, grid, n, m):
	ans = (x >= 0 and x < n) and (y >= 0 and y < m) and (grid[x][y] != '#')
	return ans

def check(per, dirs, grid, n, m, ci, cj):
	for step in dirs:
		if is_valid(ci + mov[per[step]][1], cj + mov[per[step]][0], grid, n, m):
			ci += mov[per[step]][1]
			cj += mov[per[step]][0]
			if grid[ci][cj] == 'E':
				return 1
		else:
			return 0
	return 0
(n, m) = map(int, input().split())
grid = []
for i in range(n):
	grid.append(input())
for i in range(n):
	for j in range(m):
		if grid[i][j] == 'S':
			(ci, cj) = (i, j)
			break
dirs = [int(ch) for ch in input()]
perms = [list(ob) for ob in list(itertools.permutations(['U', 'D', 'L', 'R']))]
ans = 0
for per in perms:
	(tci, tcj) = (ci, cj)
	if check(per, dirs, grid, n, m, tci, tcj) > 0:
		ans += 1
print(ans)


def trace(maze, sol, cur):
	try:
		if cur[0] < 0 or cur[1] < 0:
			return False
		elif maze[cur[0]][cur[1]] == '#':
			return False
		elif maze[cur[0]][cur[1]] == 'E':
			return True
		elif sol == []:
			return False
		nxt = sol[0]
		if nxt == 'u':
			return trace(maze, sol[1:], [cur[0] - 1, cur[1]])
		elif nxt == 'd':
			return trace(maze, sol[1:], [cur[0] + 1, cur[1]])
		elif nxt == 'l':
			return trace(maze, sol[1:], [cur[0], cur[1] - 1])
		elif nxt == 'r':
			return trace(maze, sol[1:], [cur[0], cur[1] + 1])
	except IndexError:
		return False
[n, m] = [int(i) for i in input().split()]
maze = []
start = [0, 0]
for i in range(n):
	maze.append(list(input()))
	if 'S' in maze[-1]:
		start = [i, maze[-1].index('S')]
d = [int(i) for i in list(input())]
c = 0
p = ['dlur', 'ruld', 'uldr', 'udrl', 'ulrd', 'rlud', 'urdl', 'rldu', 'lurd', 'dulr', 'ldur', 'rdlu', 'lrdu', 'drlu', 'lrud', 'ldru', 'udlr', 'durl', 'drul', 'dlru', 'rdul', 'ludr', 'rudl', 'urld']
for i in p:
	if trace(maze, [i[char] for char in d], start):
		c += 1
print(c)


(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)


from itertools import permutations
(rows, cols) = [int(x) for x in input().split()]
grid = [input() for _ in range(rows)]
route = input()
directions = [[0, 1], [-1, 0], [0, -1], [1, 0]]
begin_exit = [[-1, -1], [-1, -1]]
for i in range(rows):
	for j in range(cols):
		if grid[i][j] == 'S':
			begin_exit[0][0] = i
			begin_exit[0][1] = j
		elif grid[i][j] == 'E':
			begin_exit[1][0] = i
			begin_exit[1][1] = j
ans = 0
for d in permutations(directions):
	(x, y) = (begin_exit[0][0], begin_exit[0][1])
	for r in route:
		dr = d[int(r)]
		x += dr[0]
		y += dr[1]
		if x == begin_exit[1][0] and y == begin_exit[1][1]:
			ans += 1
			break
		if not 0 <= x < rows or not 0 <= y < cols or grid[x][y] == '#':
			break
print(ans)


import math
import itertools

def main():
	(n, m) = list(map(int, input().split()))
	a = []
	start = None
	for i in range(n):
		line = input()
		j = line.find('S')
		if j != -1:
			start = (j, i)
		a.append(line)
	s = input()
	v = [(-1, 0), (1, 0), (0, -1), (0, 1)]
	res = 0
	for d in itertools.permutations(v):
		if check(a, start, s, d, n, m):
			res += 1
	print(res)

def check(a, start, s, d, n, m):
	(x, y) = start
	for c in s:
		(dx, dy) = d[int(c)]
		x += dx
		y += dy
		if x < 0 or x >= m or y < 0 or (y >= n):
			return False
		if a[y][x] == 'E':
			return True
		if a[y][x] == '#':
			return False
	return False
try:
	main()
except KeyboardInterrupt as e:
	pass


from itertools import permutations

def main():
	(n, m) = map(int, input().split())
	field = []
	start = (-1, -1)
	end = (-1, -1)
	for i in range(n):
		field.append(input())
		if field[i].find('S') != -1:
			start = (i, field[i].find('S'))
		if field[i].find('E') != -1:
			end = (i, field[i].find('E'))
	cmds = [int(i) for i in input()]
	directions = ['D', 'L', 'R', 'U']
	cnt = 0
	for dirs in permutations(directions, 4):
		(y, x) = start
		fail = False
		ok = False
		for cmd in cmds:
			if dirs[cmd] == 'D':
				y += 1
			elif dirs[cmd] == 'U':
				y -= 1
			elif dirs[cmd] == 'L':
				x -= 1
			else:
				x += 1
			if x < 0 or x >= m or y < 0 or (y >= n) or (field[y][x] == '#'):
				fail = True
				break
			if (y, x) == end:
				ok = True
				break
		if fail:
			continue
		if ok:
			cnt += 1
			continue
		if (y, x) == end:
			cnt += (y, x) == end
	print(cnt)
main()


import itertools
dir = [(1, 0), (0, 1), (0, -1), (-1, 0)]
(n, m) = map(int, input().split())
map = [input() for _ in range(n)]
d = input()
(s_i, s_j) = (-1, -1)
for i in range(n):
	for j in range(m):
		if map[i][j] == 'S':
			s_i = i
			s_j = j

def go(p):
	si = s_i
	sj = s_j
	for c in d:
		id = p[int(c)]
		si += dir[id][0]
		sj += dir[id][1]
		if si < 0 or si >= n or sj < 0 or (sj >= m) or (map[si][sj] == '#'):
			return 0
		if map[si][sj] == 'E':
			return 1
	return 0
print(sum((go(p) for p in itertools.permutations([0, 1, 2, 3]))))


(n, m) = map(int, input().split())
field = [list(input()) for i in range(n)]
commands = list(map(int, list(input())))
perm = []
ans = 0
dx = (-1, 1, 0, 0)
dy = (0, 0, -1, 1)
start = (0, 0)
for i in range(n):
	for j in range(m):
		if field[i][j] == 'S':
			start = (i, j)
			field[i][j] = '.'

def check():
	global ans
	(x, y) = start
	for i in commands:
		d = perm[i]
		x = x + dx[d]
		y = y + dy[d]
		if x < 0 or x >= n or y < 0 or (y >= m) or (field[x][y] == '#'):
			return
		if field[x][y] == 'E':
			ans += 1
			return

def rec(i):
	if i == 4:
		check()
	for j in range(4):
		if j not in perm:
			perm.append(j)
			rec(i + 1)
			perm.pop()
rec(0)
print(ans)


from itertools import permutations
maze = []
(n, m) = [int(i) for i in input().split(' ')]
for i in range(n):
	maze.append(list(str(input())))
p = list(permutations([0, 1, 2, 3]))
ins = list(str(input()))
start = [0, 0]
end = [0, 0]
result = 0
for i in range(n):
	for j in range(m):
		if maze[i][j] == 'S':
			start = [i, j]
		elif maze[i][j] == 'E':
			end = [i, j]
for k in range(24):
	(l, r, u, d) = (p[k][0], p[k][1], p[k][2], p[k][3])
	cur = start[:]
	action = 0
	for x in ins:
		if x == '0':
			action = l
		elif x == '1':
			action = r
		elif x == '2':
			action = u
		elif x == '3':
			action = d
		if action == 0:
			cur[0] += 1
		elif action == 1:
			cur[0] -= 1
		elif action == 2:
			cur[1] += 1
		elif action == 3:
			cur[1] -= 1
		if cur == end:
			result += 1
			break
		elif cur[0] < 0 or cur[1] < 0 or cur[0] >= n or (cur[1] >= m):
			break
		elif maze[cur[0]][cur[1]] == '#':
			break
print(result)


from itertools import permutations
r = [int(x) for x in input().split(' ')]
h = r[0]
w = r[1]
m = []
n = 0
for i in range(h):
	m.append(input())
for row in range(h):
	if 'S' in m[row]:
		starty = row
		startx = m[row].index('S')
ins = input()

def followinstructions(mapping):
	y = starty
	x = startx
	for i in ins:
		x += mapping[int(i)][0]
		y += mapping[int(i)][1]
		if x >= 0 and x < w:
			if y >= 0 and y < h:
				if m[y][x] != '#':
					if m[y][x] == 'E':
						return True
				else:
					return False
			else:
				return False
		else:
			return False
	return False
mappings = permutations([(0, 1), (0, -1), (1, 0), (-1, 0)], 4)
for mapping in mappings:
	if followinstructions(mapping):
		n += 1
print(n)


(n, m) = map(int, input().split())
a = [[0] * m for t in range(n)]
begeinX = 0
beginY = 0
flag = True
for q in range(0, n):
	a[q] = input()
for z in range(0, n):
	for x in range(0, m):
		if a[z][x] == 'S':
			beginX = x
			beginY = z
begin = [beginX, beginY]
s = input()
l = len(s)
number = 0
left = ['3', '3', '3', '3', '3', '3', '2', '2', '2', '2', '2', '2', '1', '1', '1', '1', '1', '1', '0', '0', '0', '0']
righ = ['2', '2', '1', '1', '0', '0', '3', '3', '1', '1', '0', '0', '3', '3', '2', '2', '0', '0', '3', '3', '2', '2']
goup = ['1', '0', '2', '0', '1', '2', '1', '0', '3', '0', '1', '3', '2', '0', '3', '0', '2', '3', '1', '2', '1', '3']
down = ['0', '1', '0', '2', '2', '1', '0', '1', '0', '3', '3', '1', '0', '2', '0', '3', '3', '2', '2', '1', '3', '1']
left2 = ['0', '0']
righ2 = ['1', '1']
goup2 = ['2', '3']
down2 = ['3', '2']
for k in range(0, 22):
	beginX = begin[0]
	beginY = begin[1]
	for i in range(0, l):
		if s[i] == left[k]:
			if beginX > 0:
				beginX -= 1
			else:
				break
		if s[i] == righ[k]:
			if beginX < m - 1:
				beginX += 1
			else:
				break
		if s[i] == goup[k]:
			if beginY < n - 1:
				beginY += 1
			else:
				break
		if s[i] == down[k]:
			if beginY > 0:
				beginY -= 1
			else:
				break
		if a[beginY][beginX] == '#':
			break
		if a[beginY][beginX] == 'E':
			number += 1
			break
for p in range(0, 2):
	beginX = begin[0]
	beginY = begin[1]
	for j in range(0, l):
		if s[j] == left2[p]:
			if beginX > 0:
				beginX -= 1
			else:
				break
		if s[j] == righ2[p]:
			if beginX < m - 1:
				beginX += 1
			else:
				break
		if s[j] == goup2[p]:
			if beginY < n - 1:
				beginY += 1
			else:
				break
		if s[j] == down2[p]:
			if beginY > 0:
				beginY -= 1
			else:
				break
		if a[beginY][beginX] == '#':
			break
		if a[beginY][beginX] == 'E':
			number += 1
			break
print(number)


def list_output(s):
	print(' '.join(map(str, s)))

def list_input(s='int'):
	if s == 'int':
		return list(map(int, input().split()))
	elif s == 'float':
		return list(map(float, input().split()))
	return list(map(str, input().split()))
(n, m) = map(int, input().split())
M = list()
for i in range(n):
	M.append(input())
tmp = input().rstrip()
seq = list()
for x in tmp:
	seq.append(ord(x) - ord('0'))
(sx, sy) = (-1, -1)
(gx, gy) = (-1, -1)
for i in range(n):
	for j in range(m):
		if M[i][j] == 'S':
			(sx, sy) = (i, j)
		elif M[i][j] == 'E':
			(gx, gy) = (i, j)
from itertools import permutations
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
res = 0
for p in permutations([0, 1, 2, 3]):
	(x, y) = (sx, sy)
	for s in seq:
		x += dx[p[s]]
		y += dy[p[s]]
		if x < 0 or x >= n or y < 0 or (y >= m):
			break
		if M[x][y] == '#':
			break
		if x == gx and y == gy:
			res += 1
			break
print(res)


import sys

class maze:
	starting = 'S'
	exiting = 'E'
	obstacle = '#'

	def __init__(self, maze_map):
		self.cells = list()
		for i in range(len(maze_map)):
			self.cells.append([])
			for j in range(len(maze_map[i])):
				self.cells[i].append(maze_map[i][j])
				if maze_map[i][j] == maze.starting:
					self.start = (i, j)

class robot:
	right = 0
	up = 1
	left = 2
	down = 3
	dp = [(0, 1), (-1, 0), (0, -1), (1, 0)]

	def __init__(self, maze):
		self.maze = maze
		self.position = maze.start

	def reset(self):
		self.position = self.maze.start

	def move(self, direction):
		self.position = (self.position[0] + robot.dp[direction][0], self.position[1] + robot.dp[direction][1])
		i = self.position[0]
		j = self.position[1]
		if i < 0 or i >= len(self.maze.cells) or j < 0 or (j >= len(self.maze.cells[0])) or (self.maze.cells[i][j] == maze.obstacle):
			return False
		else:
			return True

	def is_exit(self):
		if self.maze.cells[self.position[0]][self.position[1]] == maze.exiting:
			return True
		else:
			return False
input()
maze_map = [i.strip() for i in sys.stdin.readlines()]
commands = maze_map[-1]
maze_map = maze_map[:-1]
the_maze = maze(maze_map)
the_robot = robot(the_maze)
mappings = set()
for i in range(4):
	for j in range(4):
		for k in range(4):
			for l in range(4):
				if len({i, j, k, l}) == 4:
					mappings.add((i, j, k, l))
success = 0
for mapping in mappings:
	the_robot.reset()
	for command in commands:
		if not the_robot.move(mapping[int(command)]):
			break
		if the_robot.is_exit():
			success += 1
			break
print(success)


(n, m) = map(int, input().split())
matrix = []
(s_i, s_j) = (0, 0)
for i in range(n):
	matrix.append(list(input()))
	if 'S' in matrix[-1]:
		s_i = i
		s_j = matrix[-1].index('S')

def run(instructions, rules):
	i = s_i
	j = s_j
	for elem in instructions:
		if rules[elem] == 'u':
			i -= 1
		elif rules[elem] == 'd':
			i += 1
		elif rules[elem] == 'r':
			j += 1
		elif rules[elem] == 'l':
			j -= 1
		if i >= n or i < 0 or j >= m or (j < 0):
			return False
		if matrix[i][j] == '#':
			return False
		elif matrix[i][j] == 'E':
			return True
	return False
instr = input()
poss = 0
dirs = ['r', 'u', 'd', 'l']
for x in dirs:
	for y in dirs:
		for z in dirs:
			for p in dirs:
				if len({x, y, z, p}) == 4:
					if run(instr, {'0': x, '1': y, '2': z, '3': p}):
						poss += 1
print(poss)


import itertools
n = input().split(' ')
n = list(map(int, n))
border = ['#'] * (n[1] + 2)
maze = []
maze.append(border)
for i in range(0, n[0]):
	path = input()
	path = list(path)
	path.insert(0, '#')
	path.extend('#')
	maze.append(path)
	try:
		sy = path.index('S')
		sx = i + 1
	except ValueError:
		pass
maze.append(border)
order = input()
order = list(map(int, order))
cont = 0
walks = [(-1, 0), (1, 0), (0, 1), (0, -1)]
for i in itertools.permutations(walks):
	x = sx
	y = sy
	for k in order:
		dr = i[k]
		x += dr[0]
		y += dr[1]
		if maze[x][y] == 'E':
			cont += 1
			break
		elif maze[x][y] == '#':
			break
print(cont)


from itertools import permutations
(n, m) = 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,) = 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(range(4)):
	ans += solve(p)
print(ans)


import itertools

def processing(maze, row, col, path):
	(n, m) = (len(maze), len(maze[0]))
	for i in range(len(path)):
		if path[i] == 'U':
			row -= 1
		elif path[i] == 'R':
			col += 1
		elif path[i] == 'D':
			row += 1
		elif path[i] == 'L':
			col -= 1
		if not (0 <= row < n and 0 <= col < m) or maze[row][col] == '#':
			return False
		elif maze[row][col] == 'E':
			return True
	return False

def transform_path(orig_path, dir):
	return [dir[int(orig_path[k])] for k in range(len(orig_path))]
(n, m) = map(int, input().split())
maze = []
for i in range(n):
	maze.append(input())
	if maze[-1].count('S') != 0:
		pos = [i, maze[-1].index('S')]
cnt = 0
dir = ['U', 'R', 'D', 'L']
orig_path = input()
for d in itertools.permutations(['U', 'R', 'D', 'L']):
	if processing(maze, *pos, transform_path(orig_path, d)):
		cnt += 1
print(cnt)


(n, m) = list(map(int, input().split()))
matrix = [input() for i in range(n)]
program = input()
num_of_right = 0
for u in range(4):
	for d in range(4):
		if d == u:
			continue
		for l in range(4):
			if l == d or l == u:
				continue
			for r in range(4):
				if r == l or r == u or r == d:
					continue
				directions = {str(u): [1, 0], str(d): [-1, 0], str(r): [0, 1], str(l): [0, -1]}
				coords = [0, 0]
				for i in range(n):
					if 'S' in matrix[i]:
						coords = [i, matrix[i].index('S')]
						break
				result = 0
				for command in program:
					coords = [coords[0] + directions[command][0], coords[1] + directions[command][1]]
					if coords[0] < 0 or coords[0] >= n or coords[1] < 0 or (coords[1] >= m):
						break
					current = matrix[coords[0]][coords[1]]
					if current == '#':
						break
					if current == 'E':
						result = 1
						break
				if result:
					num_of_right += 1
print(num_of_right)


import itertools
(n, m) = list(map(int, input().split()))
a = []
for i in range(n):
	x = input()
	a.append(x)
oper = list(map(int, input()))
(s_x, s_y, e_x, e_y) = (0, 0, 0, 0)
for i in range(n):
	for j in range(m):
		if a[i][j] == 'S':
			(s_x, s_y) = (i, j)
		elif a[i][j] == 'E':
			(e_x, e_y) = (i, j)

def valid(x, y):
	if x < 0 or y < 0 or x >= n or (y >= m):
		return False
	if a[x][y] == '#':
		return False
	return True
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
ans = 0
for i in itertools.permutations([0, 1, 2, 3]):
	fl = True
	(tmp_x, tmp_y) = (s_x, s_y)
	for j in range(len(oper)):
		next_x = tmp_x + dx[i[oper[j]]]
		next_y = tmp_y + dy[i[oper[j]]]
		if not valid(next_x, next_y):
			fl = False
			break
		(tmp_x, tmp_y) = (next_x, next_y)
		if tmp_x == e_x and tmp_y == e_y:
			ans += 1
			break
print(ans)


import itertools
(n, m) = map(int, input().split())
data = [input().strip() for i in range(n)]
move = list(map(int, list(input().strip())))

def valid(data, moves):
	(x, y) = (0, 0)
	for (i, row) in enumerate(data):
		for (j, ch) in enumerate(row):
			if ch == 'S':
				(x, y) = (i, j)
	for m in moves:
		if m == 'N':
			x -= 1
		if m == 'E':
			y -= 1
		if m == 'W':
			y += 1
		if m == 'S':
			x += 1
		if not (0 <= x < len(data) and 0 <= y < len(data[0])):
			return False
		if data[x][y] == '#':
			return False
		if data[x][y] == 'E':
			return True
	return False
ans = 0
for x in itertools.permutations(range(4)):
	direction = {a: b for (a, b) in zip(x, list('NEWS'))}
	moves = list(map(lambda x: direction[x], move))
	if valid(data, moves):
		ans += 1
print(ans)


import itertools as it
(n, m) = map(int, input().split())
board = [['#' for _ in range(m + 2)]]
for _ in range(n):
	board += [['#'] + list(input()) + ['#']]
board += [['#' for _ in range(m + 2)]]
route = input()
D = {0: (-1, 0), 1: (1, 0), 2: (0, -1), 3: (0, 1)}
s_pos = None
for i in range(n + 2):
	for j in range(m + 2):
		if board[i][j] == 'S':
			s_pos = (i, j)
result = 0
for mapping in it.permutations(range(4)):
	pos = s_pos
	for i in route:
		pos = (pos[0] + D[mapping[int(i)]][0], pos[1] + D[mapping[int(i)]][1])
		if board[pos[0]][pos[1]] == 'E':
			result += 1
			break
		elif board[pos[0]][pos[1]] == '#':
			break
print(result)


from itertools import permutations as pm
(n, m) = map(int, input().split())
a = []
for i in range(n):
	a.append(list(input()))
s = input()

def move(d):
	for i in range(n):
		for j in range(m):
			if a[i][j] == 'S':
				current = [i, j]
			if a[i][j] == 'E':
				end = [i, j]
	for i in s:
		if current == end:
			return True
		fx = current[0] + d[i][0]
		fy = current[1] + d[i][1]
		if 0 <= fx < n and 0 <= fy < m:
			if a[fx][fy] == '#':
				return False
		else:
			return False
		current[0] = fx
		current[1] = fy
	if current == end:
		return True
	return False
ans = 0
p = list(pm([(1, 0), (0, 1), (-1, 0), (0, -1)]))
for i in p:
	if move({str(j): i[j] for j in range(4)}):
		ans += 1
print(ans)


l = ['0123', '0132', '0213', '0231', '0312', '0321', '1023', '1032', '1203', '1230', '1302', '1320', '2013', '2031', '2103', '2130', '2301', '2310', '3012', '3021', '3102', '3120', '3201', '3210']
(n, m) = map(int, input().split())
grid = [0] * n
for i in range(n):
	grid[i] = list(input())
	if 'S' in grid[i]:
		sx = i
		sy = grid[i].index('S')
direc = list(map(int, list(input())))
ans = 0
sxog = sx
syog = sy
for i in l:
	sx = sxog
	sy = syog
	found = 0
	for j in range(len(direc)):
		if i[direc[j]] == '0':
			sx += 1
		if i[direc[j]] == '1':
			sx -= 1
		if i[direc[j]] == '2':
			sy += 1
		if i[direc[j]] == '3':
			sy -= 1
		if sx < 0 or sy < 0 or sx >= n or (sy >= m):
			break
		new = grid[sx][sy]
		if new == '#':
			break
		if new == 'E':
			found = 1
			break
	if found == 1:
		ans += 1
print(ans)


from itertools import permutations as p
(n, m) = input().split()
(n, m) = (int(n), int(m))
maze = []
for i in range(n):
	l = input()
	if 'S' in l:
		coorS = [i, l.index('S')]
	if 'E' in l:
		coorE = [i, l.index('E')]
	maze.append(l)
val = input()
sol = 0
save = list(coorS)
for f in p('0123', 4):
	(l, r, u, d) = (f[0], f[1], f[2], f[3])
	for k in val:
		if l == k:
			if coorS[1] == 0:
				break
			elif maze[coorS[0]][coorS[1] - 1] == '#':
				break
			else:
				coorS = list([coorS[0], coorS[1] - 1])
		elif r == k:
			if coorS[1] == m - 1:
				break
			elif maze[coorS[0]][coorS[1] + 1] == '#':
				break
			else:
				coorS = list([coorS[0], coorS[1] + 1])
		elif u == k:
			if coorS[0] == 0:
				break
			elif maze[coorS[0] - 1][coorS[1]] == '#':
				break
			else:
				coorS = list([coorS[0] - 1, coorS[1]])
		elif d == k:
			if coorS[0] == n - 1:
				break
			elif maze[coorS[0] + 1][coorS[1]] == '#':
				break
			else:
				coorS = list([coorS[0] + 1, coorS[1]])
		if coorS == coorE:
			sol += 1
			break
	coorS = list(save)
print(sol)


(n, m) = map(int, input().split())
y = []
for i in range(n):
	x = list(map(str, input()))
	y.append(x)
s = input()
a = [[0, 1, 2, 3], [0, 1, 3, 2], [0, 2, 1, 3], [0, 2, 3, 1], [0, 3, 1, 2], [0, 3, 2, 1], [1, 0, 2, 3], [1, 0, 3, 2], [1, 2, 0, 3], [1, 2, 3, 0], [1, 3, 2, 0], [1, 3, 0, 2], [2, 0, 1, 3], [2, 0, 3, 1], [2, 1, 0, 3], [2, 1, 3, 0], [2, 3, 0, 1], [2, 3, 1, 0], [3, 0, 1, 2], [3, 0, 2, 1], [3, 1, 2, 0], [3, 1, 0, 2], [3, 2, 0, 1], [3, 2, 1, 0]]
q = [[1, 3, 2, 0]]
(z, end) = ([0, 0], [0, 0])
for i in range(n):
	for j in range(m):
		if y[i][j] == 'S':
			z = [i, j]
		if y[i][j] == 'E':
			end = [i, j]
(q1, q2) = (z[0], z[1])
count = 0
for i in a:
	(left, right, up, down) = (str(i[0]), str(i[1]), str(i[2]), str(i[3]))
	ind = True
	begin = [q1, q2]
	for j in range(len(s)):
		if s[j] == left:
			begin[1] -= 1
		elif s[j] == right:
			begin[1] += 1
		elif s[j] == up:
			begin[0] -= 1
		elif s[j] == down:
			begin[0] += 1
		if begin[0] < 0 or begin[0] >= n or begin[1] < 0 or (begin[1] >= m) or (y[begin[0]][begin[1]] == '#'):
			ind = False
			break
		if begin == end and ind == True:
			break
	if ind and begin == end:
		count += 1
print(count)


from itertools import permutations
(m, n) = map(int, input().split())
a = []
for i in range(m):
	b = input()
	a.append(list(b))
s = input()
si = 0
sj = 0
for i in range(m):
	for j in range(n):
		if a[i][j] == 'S':
			si = i
			sj = j
d = list(permutations([0, 1, 2, 3]))
c = 0
for u in d:
	z = dict()
	z[u[0]] = 'u'
	z[u[1]] = 'd'
	z[u[2]] = 'l'
	z[u[3]] = 'r'
	i = si
	j = sj
	for k in s:
		if z[int(k)] == 'u':
			i -= 1
		elif z[int(k)] == 'd':
			i += 1
		elif z[int(k)] == 'l':
			j -= 1
		elif z[int(k)] == 'r':
			j += 1
		if i < 0 or j < 0 or i >= m or (j >= n):
			break
		if a[i][j] == '#':
			break
		if a[i][j] == 'E':
			c += 1
			break
print(c)


from sys import stdin as cin
from sys import stdout as cout

def main():
	(n, m) = map(int, cin.readline().split())
	a = [''] * n
	for i in range(n):
		a[i] = cin.readline()
	s = cin.readline().split()[0]
	for i in range(n):
		for j in range(m):
			if a[i][j] == 'S':
				xs = j
				ys = i
			elif a[i][j] == 'E':
				xe = j
				ye = i
	q = ['lrdu', 'lrud', 'ldru', 'ldur', 'lurd', 'ludr', 'rldu', 'rlud', 'rdlu', 'rdul', 'ruld', 'rudl', 'dlru', 'dlur', 'drlu', 'drul', 'dulr', 'durl', 'ulrd', 'uldr', 'urld', 'urdl', 'udlr', 'udrl']
	o = 0
	for ss in q:
		x = xs
		y = ys
		f = 1
		for i in s:
			c = ss[int(i)]
			if c == 'l':
				if x == 0 or a[y][x - 1] == '#':
					f = 0
					break
				else:
					x -= 1
			elif c == 'r':
				if x == m - 1 or a[y][x + 1] == '#':
					f = 0
					break
				else:
					x += 1
			elif c == 'u':
				if y == 0 or a[y - 1][x] == '#':
					f = 0
					break
				else:
					y -= 1
			elif y == n - 1 or a[y + 1][x] == '#':
				f = 0
				break
			else:
				y += 1
			if x == xe and y == ye:
				break
		if x == xe and y == ye:
			o += f
	print(o)
main()


poss = [(0, 1, 2, 3), (0, 1, 3, 2), (0, 2, 1, 3), (0, 2, 3, 1), (0, 3, 1, 2), (0, 3, 2, 1), (1, 0, 2, 3), (1, 0, 3, 2), (1, 2, 0, 3), (1, 2, 3, 0), (1, 3, 0, 2), (1, 3, 2, 0), (2, 0, 1, 3), (2, 0, 3, 1), (2, 1, 0, 3), (2, 1, 3, 0), (2, 3, 0, 1), (2, 3, 1, 0), (3, 0, 1, 2), (3, 0, 2, 1), (3, 1, 0, 2), (3, 1, 2, 0), (3, 2, 0, 1), (3, 2, 1, 0)]
(n, m) = map(int, input().split())
maze = []
start = []
for i in range(n):
	x = []
	count = 0
	for j in input():
		if j == 'S':
			start = [i, count]
		count += 1
		x.append(j)
	maze.append(x)
path = input()
ans_count = 0

def check(x):
	global ans_count
	global start
	con = {x[0]: 'U', x[1]: 'D', x[2]: 'L', x[3]: 'R'}
	new_path = ''
	for i in path:
		new_path += con[int(i)]
	(cx, cy) = (start[0], start[1])
	for i in new_path:
		if i == 'U':
			cy -= 1
		elif i == 'D':
			cy += 1
		elif i == 'R':
			cx += 1
		elif i == 'L':
			cx -= 1
		if cx < 0 or cx >= n or cy < 0 or (cy >= m):
			return
		elif maze[cx][cy] == '#':
			return
		elif maze[cx][cy] == 'E':
			ans_count += 1
			return
for i in poss:
	check(i)
print(ans_count)


(n, m) = map(int, input().split())
lab = []
for i in range(n):
	lab.append(list(input()))
	if 'S' in lab[-1]:
		rpp = [i, lab[-1].index('S')]
st = input()
cl = 'urdl'
co = 0
for c1 in cl:
	for c2 in cl:
		if c2 == c1:
			continue
		for c3 in cl:
			if c3 == c2 or c3 == c1:
				continue
			for c4 in cl:
				if c4 in (c1, c2, c3):
					continue
				rp = rpp[:]
				for l in st:
					l = (c1, c2, c3, c4)[int(l)]
					if l == 'u':
						if rp[0] - 1 >= 0:
							if lab[rp[0] - 1][rp[1]] != '#':
								if lab[rp[0] - 1][rp[1]] == 'E':
									co += 1
									break
								rp[0] -= 1
							else:
								break
						else:
							break
					elif l == 'r':
						if rp[1] + 1 < m:
							if lab[rp[0]][rp[1] + 1] != '#':
								if lab[rp[0]][rp[1] + 1] == 'E':
									co += 1
									break
								rp[1] += 1
							else:
								break
						else:
							break
					elif l == 'd':
						if rp[0] + 1 < n:
							if lab[rp[0] + 1][rp[1]] != '#':
								if lab[rp[0] + 1][rp[1]] == 'E':
									co += 1
									break
								rp[0] += 1
							else:
								break
						else:
							break
					elif rp[1] - 1 >= 0:
						if lab[rp[0]][rp[1] - 1] != '#':
							if lab[rp[0]][rp[1] - 1] == 'E':
								co += 1
								break
							rp[1] -= 1
						else:
							break
					else:
						break
print(co)


get = lambda : list(map(int, input().split()))
(n, m) = get()
M = []
from itertools import permutations

def follow(x, s, start):
	pos = start
	for i in s:
		pos += x[int(i)]
		if not (0 <= pos.real < m and 0 <= pos.imag < n):
			return False
		q = M[int(pos.imag)][int(pos.real)]
		if q == 'E':
			return True
		if q == '#':
			return False
for i in range(n):
	M.append(input())
	tmp = M[i].find('S')
	tmq = M[i].find('E')
	if tmp != -1:
		start = complex(tmp, i)
	if tmq != -1:
		end = complex(tmq, i)
s = input()
ans = 0
for i in permutations([1, -1, 1j, -1j]):
	if follow(dict(zip(range(4), i)), s, start):
		ans += 1
print(ans)


(n, m) = map(int, input().split())
lst = []
for x in range(n):
	lst.append(input())
array_num = list(map(int, input()))

def xxx(up, down, left, right, x, y, i):
	if lst[x][y] == 'E':
		return True
	if i == len(array_num):
		return False
	if array_num[i] == up:
		if x - 1 >= 0 and lst[x - 1][y] != '#':
			return xxx(up, down, left, right, x - 1, y, i + 1)
	if array_num[i] == down:
		if x + 1 <= n - 1 and lst[x + 1][y] != '#':
			return xxx(up, down, left, right, x + 1, y, i + 1)
	if array_num[i] == left:
		if y - 1 >= 0 and lst[x][y - 1] != '#':
			return xxx(up, down, left, right, x, y - 1, i + 1)
	if array_num[i] == right:
		if y + 1 <= m - 1 and lst[x][y + 1] != '#':
			return xxx(up, down, left, right, x, y + 1, i + 1)
for x in range(n):
	for y in range(m):
		if lst[x][y] == 'S':
			(i, j) = (x, y)
			break
k = 0
if xxx(1, 2, 3, 0, i, j, 0):
	k += 1
if xxx(1, 2, 0, 3, i, j, 0):
	k += 1
if xxx(1, 3, 2, 0, i, j, 0):
	k += 1
if xxx(1, 3, 0, 2, i, j, 0):
	k += 1
if xxx(1, 0, 2, 3, i, j, 0):
	k += 1
if xxx(1, 0, 3, 2, i, j, 0):
	k += 1
if xxx(2, 1, 3, 0, i, j, 0):
	k += 1
if xxx(2, 1, 0, 3, i, j, 0):
	k += 1
if xxx(2, 3, 1, 0, i, j, 0):
	k += 1
if xxx(2, 3, 0, 1, i, j, 0):
	k += 1
if xxx(2, 0, 1, 3, i, j, 0):
	k += 1
if xxx(2, 0, 3, 1, i, j, 0):
	k += 1
if xxx(3, 1, 2, 0, i, j, 0):
	k += 1
if xxx(3, 1, 0, 2, i, j, 0):
	k += 1
if xxx(3, 2, 1, 0, i, j, 0):
	k += 1
if xxx(3, 2, 0, 1, i, j, 0):
	k += 1
if xxx(3, 0, 1, 2, i, j, 0):
	k += 1
if xxx(3, 0, 2, 1, i, j, 0):
	k += 1
if xxx(0, 1, 2, 3, i, j, 0):
	k += 1
if xxx(0, 1, 3, 2, i, j, 0):
	k += 1
if xxx(0, 2, 1, 3, i, j, 0):
	k += 1
if xxx(0, 2, 3, 1, i, j, 0):
	k += 1
if xxx(0, 3, 1, 2, i, j, 0):
	k += 1
if xxx(0, 3, 2, 1, i, j, 0):
	k += 1
print(k)


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)
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)


from itertools import permutations
(n, m) = (int(c) for c in input().split())
s = '#' * (m + 2)
for i in range(n):
	s += '#' + input().strip() + '#'
s += '#' * (m + 2)
ins = ['0123'.find(c) for c in input().strip()]
op = [lambda p: p + 1, lambda p: p - 1, lambda p: p + m + 2, lambda p: p - m - 2]
c = 0
for o in permutations(op):
	p = s.find('S')
	for i in ins:
		p = o[i](p)
		if s[p] == '#':
			break
		elif s[p] == 'E':
			c += 1
			break
print(c)


import itertools
import sys

def is_valid_path(board, path):
	(x, y) = (-1, -1)
	for (i, row) in enumerate(board):
		if 'S' in row:
			(x, y) = (row.index('S'), i)
	for step in path:
		x += 1 if step == 'E' else 0
		x += -1 if step == 'W' else 0
		y += 1 if step == 'S' else 0
		y += -1 if step == 'N' else 0
		if x < 0 or x >= len(board[0]):
			return False
		if y < 0 or y >= len(board):
			return False
		if board[y][x] == '#':
			return False
		if board[y][x] == 'E':
			return True
	return False
lines = [l.strip() for l in sys.stdin.readlines()]
(row_count, column_count) = lines[0].split()
board = [l for l in lines[1:-1]]
path = [s for s in lines[-1]]
valid = 0
for key in itertools.permutations('NSEW', 4):
	mapped_path = [key[int(s)] for s in path]
	valid += 1 if is_valid_path(board, mapped_path) else 0
print(valid)


def o1(d):
	global x, y, t
	(x2, y2) = (x, y)
	for i in d:
		if i == '0':
			y2 += 1
		elif i == '1':
			x2 += 1
		elif i == '2':
			y2 -= 1
		else:
			x2 -= 1
		if x2 < 0 or x2 >= n or y2 < 0 or (y2 >= m):
			return False
		elif t[x2][y2] == '#':
			return False
		elif t[x2][y2] == 'E':
			return True
	return False
(n, m) = map(int, input().split())
te = 0
t = []
for i in range(n):
	t.append(list(input()))
(x, y) = (None, None)
for i in range(n):
	for j in range(m):
		if t[i][j] == 'S':
			x = i
			y = j
			break
	if x != None:
		break
o = input()
r = []
a = [0, 1, 2, 3]
for i in range(4):
	b = a[:i] + a[i + 1:]
	for i2 in range(3):
		c = b[:i2] + b[i2 + 1:]
		for j in range(2):
			d = c[:j] + c[j + 1:]
			r.append([a[i], b[i2], c[j], d[0]])
for i in r:
	f = ''
	for j in o:
		f = f + str(i[int(j)])
	te += o1(f)
print(te)


def func(comb, curposY, curposX):
	for i in code:
		i = int(i)
		if comb[i] == 0:
			curposY += 1
			if curposY >= a:
				return 0
			elif field[curposY][curposX] == '#':
				return 0
			if field[curposY][curposX] == 'E':
				return 1
		elif comb[i] == 1:
			curposY -= 1
			if curposY < 0:
				return 0
			elif field[curposY][curposX] == '#':
				return 0
			if field[curposY][curposX] == 'E':
				return 1
		elif comb[i] == 2:
			curposX += 1
			if curposX >= len(field[0]):
				return 0
			elif field[curposY][curposX] == '#':
				return 0
			if field[curposY][curposX] == 'E':
				return 1
		elif comb[i] == 3:
			curposX -= 1
			if curposX < 0:
				return 0
			elif field[curposY][curposX] == '#':
				return 0
			if field[curposY][curposX] == 'E':
				return 1
	return 0
a = input().split(' ')
a = int(a[0])
counter = 0
field = []
curposY = -1
curposX = -1
for i in range(0, a, 1):
	field.append(input())
for i in range(0, a, 1):
	for j in range(0, len(field[0]), 1):
		if field[i][j] == 'S':
			curposY = i
			curposX = j
code = input()
comb = [-1, -1, -1, -1]
for i in range(0, 4, 1):
	comb[0] = i
	for j in range(0, 4, 1):
		if j != i:
			comb[1] = j
			for k in range(0, 4, 1):
				if k != i and k != j:
					comb[2] = k
					for p in range(0, 4, 1):
						if p != i and p != j and (p != k):
							comb[3] = p
							counter += int(func(comb, curposY, curposX))
print(counter)


(n, m) = map(int, input().split())
lab = [input() for i in range(n)]
commands = input()
for (rowi, row) in enumerate(lab):
	if 'S' in row:
		startposx = rowi
		startposy = row.index('S')
		break
combinations = []
nc = 4
combination = [0] * nc

def fill_combinations(i):
	if i == nc:
		combinations.append(combination[:])
	for j in range(nc):
		if j not in combination[:i]:
			combination[i] = j
			fill_combinations(i + 1)
fill_combinations(0)
ans = 0
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for correspondence in combinations:
	x = startposx
	y = startposy
	exit_reached = False
	for command in commands:
		dir = directions[correspondence[int(command)]]
		x += dir[0]
		y += dir[1]
		if x < 0 or y < 0 or x == n or (y == m):
			break
		if lab[x][y] == '#':
			break
		if lab[x][y] == 'E':
			exit_reached = True
			break
	if exit_reached:
		ans += 1
print(ans)


def process(field, code, dictionary):
	(x, y) = (0, 0)
	for i in range(len(field)):
		for j in range(len(field[i])):
			if field[i][j] == 'S':
				(x, y) = (i, j)
	dx = [1, 0, -1, 0]
	dy = [0, 1, 0, -1]
	for command in code:
		x += dx[dictionary[command]]
		y += dy[dictionary[command]]
		if x < 0 or x >= len(field) or y < 0 or (y >= len(field[x])) or (field[x][y] == '#'):
			return False
		if field[x][y] == 'E':
			return True
	return False

def main():
	(n, m) = map(int, input().split())
	field = [input() for i in range(n)]
	code = input()
	ans = 0
	for U in range(4):
		for D in range(4):
			if U == D:
				continue
			for L in range(4):
				if L == U or L == D:
					continue
				for R in range(4):
					if R == U or R == L or R == D:
						continue
					if process(field, code, {'0': U, '1': D, '2': L, '3': R}):
						ans += 1
	print(ans)
main()


(n, m) = map(int, input().split())
a = [0] * n
for i in range(n):
	a[i] = input()
	for j in range(m):
		if a[i][j] == 'S':
			(x1, y1) = (i, j)
s = input()
dirr = ['0123', '0132', '0213', '0231', '0312', '0321', '1023', '1032', '1203', '1230', '1302', '1320', '2103', '2130', '2013', '2031', '2310', '2301', '3120', '3102', '3210', '3201', '3012', '3021']
ans = 0
for d in dirr:
	(x, y) = (x1, y1)
	for i in s:
		i = int(i)
		if d[i] == '0' and (x - 1 < 0 or a[x - 1][y] == '#'):
			break
		elif d[i] == '1' and (y - 1 < 0 or a[x][y - 1] == '#'):
			break
		elif d[i] == '2' and (x + 1 >= n or a[x + 1][y] == '#'):
			break
		elif d[i] == '3' and (y + 1 >= m or a[x][y + 1] == '#'):
			break
		elif d[i] == '0':
			x -= 1
		elif d[i] == '1':
			y -= 1
		elif d[i] == '2':
			x += 1
		elif d[i] == '3':
			y += 1
		if a[x][y] == 'E':
			break
	if a[x][y] == 'E':
		ans += 1
print(ans)


from itertools import permutations
a = []
for i in permutations('EWNS'):
	a.append(''.join(i))
ans = 0
(n, m) = map(int, input().split())
arr = []
for i in range(n):
	arr.append(input())
	if 'S' in arr[-1]:
		indx = i
		indy = arr[-1].index('S')

def check(x, y, sign):
	x1 = x
	y1 = y
	if sign == 'E':
		x1 += 1
	elif sign == 'W':
		x1 -= 1
	elif sign == 'N':
		y1 += 1
	else:
		y1 -= 1
	return (x1, y1)
p = input()
for dir in range(24):
	cx = indx
	cy = indy
	for i in p:
		(cx, cy) = check(cx, cy, a[dir][int(i)])
		if cx >= n or cy >= m or cx < 0 or (cy < 0):
			break
		elif arr[cx][cy] == '#':
			break
		elif arr[cx][cy] == 'E':
			ans += 1
			break
print(ans)