New Year and Buggy Bot

Bob은 2d 미로를 이동하도록 로봇을 프로그래밍했다.

미로에는 몇 개의 장애물이 있다. 빈 칸은 문자 '.'로 표시되고, 장애물은 '#'로 표시된다.

미로에는 로봇이 하나만 있다. 로봇의 시작 위치는 문자 'S'로 표시된다. 이 위치에는 장애물이 없다. 미로에는 출구도 하나만 있다. 출구의 위치는 문자 'E'로 표시된다. 이 위치에는 장애물이 없다.

로봇은 위, 왼쪽, 오른쪽 또는 아래로만 이동할 수 있다.

When Bob 로봇을 프로그래밍할 때, 그는 0부터 3까지의 숫자로 구성된 문자열을 적었다. 그는 각 숫자가 서로 다른 방향에 대응하고, 로봇이 출구에 도달하기 위해 그 방향들을 순서대로 따르도록 의도했다. 안타깝게도 그는 실제로 숫자에 방향을 할당하는 것을 잊었다.

로봇은 숫자와 서로 다른 방향 사이의 임의의 대응 관계 하나를 선택한다. 로봇은 서로 다른 숫자를 서로 다른 방향에 대응시킨다. 그런 다음 로봇은 주어진 문자열의 명령을 순서대로, 선택한 대응 관계에 따라 수행한다. 어떤 명령으로 인해 로봇이 미로의 경계 밖으로 나가거나 장애물에 부딪히게 되면, 로봇은 충돌하여 고장 난다. 로봇이 어느 시점에든 출구에 도달하면, 이후의 모든 명령을 더 이상 수행하지 않는다.

Bob은 로봇을 디버깅하는 데 어려움을 겪고 있으므로, 로봇을 출구에 도달하게 하는 숫자와 방향 사이의 대응 관계의 수를 구하려고 한다.

입력의 첫째 줄에는 미로의 크기를 나타내는 두 정수 n와 m (2 ≤ n, m ≤ 50)이 주어진다.

다음 n개의 줄에는 미로를 나타내는 문자가 각 줄마다 정확히 m개씩 주어진다.

미로의 각 문자는 '.', '#', 'S' 또는 'E'이다.

미로에는 정확히 하나의 'S'와 정확히 하나의 'E'가 있다.

마지막 줄에는 로봇에게 주어진 명령인 하나의 문자열 s (1 ≤ |s| ≤ 100)이 주어진다. s의 각 문자는 0부터 3까지의 숫자이다.

로봇을 출구에 도달하게 하는 숫자와 방향 사이의 대응 관계의 수를 하나의 정수로 출력한다.

첫 번째 예제에서 유효한 대응 관계는 뿐이며, 여기서 D는 아래쪽, L은 왼쪽, U는 위쪽, R은 오른쪽을 뜻한다.