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

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

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

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

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

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

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