B. Новый год и ручной робот
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Боб запрограммировал робота для движения по двумерному лабиринту.

В лабиринте есть препятствия. Свободные клетки обозначаются как «.», а препятствия — как «#».

В лабиринте есть один робот. Его начальная позиция обозначается буквой «S». В этой позиции нет препятствий. В лабиринте есть единственный выход. Его позиция обозначается буквой «E». В этой позиции нет препятствий.

Робот может двигаться только вверх, вниз, налево и вправо.

Когда Боб программировал робота, он выписал строчку, состоящую из цифр от 0 до 3, включительно. Он хотел сделать так, чтобы каждая цифра задавала уникальное направление, чтобы робот, следуя указаниям в данной строке, доходил бы до финиша. К сожалению, он забыл назначить цифрам направления.

Робот выберет некоторое случайное соответствие направлений цифрам. Различным цифрам робот поставит в соответствие различные направления. Затем робот выполнит данные ему инструкции, в соответствии с данной строкой и выбранному соответствию направлений цифрам. Если инструкции выведут робота за пределы лабиринта, или он врежется в препятствие, робот сломается. Если робот в любой момент времени окажется на точке с выходом, то он остановится и дальше не будет исполнять инструкции.

Боб никак не может отладить свой робот, поэтому он просит вас определить число вариантов соответствий направлений цифрам таких, что робот не сломается и доберется до выхода.

Входные данные

Первая строка содержит два целых числа n и m (2 ≤ n, m ≤ 50) — размеры лабиринта.

Следующие n строк содержат по m символов каждая и описывают лабиринт.

Каждый символ лабиринта — это «.», «#», «S» или «E».

Гарантируется, что в лабиринте ровно одна буква «S» и ровно одна буква «E».

Последняя строка содержит строку s (1 ≤ |s| ≤ 100) — команды роботу. Каждая символ строки s — цифра от 0 до 3.

Выходные данные

Выведите единственное число — количество соответствий направлений цифрам таких, что данные роботу команды приведут его к выходу.

Примеры
Входные данные
5 6
.....#
S....#
.#....
.#....
...E..
333300012
Выходные данные
1
Входные данные
6 6
......
......
..SE..
......
......
......
01232123212302123021
Выходные данные
14
Входные данные
5 3
...
.S.
###
.E.
...
3
Выходные данные
0
Примечание

В первом примере единственным подходящим соответствием будет , где D — вниз, L — влево, U — вверх, R — вправо.