18863번 - 풀 한 포기 친구 얼굴

욱제는 풀 한 포기를 뽑고 친구 얼굴을 떠올리며 쉬는 중이다. 고작 풀 한포기 뽑고 쉬는 욱제를 보고 화가 난 조교는 욱제에게 오리걸음을 시키려고 한다.

풀밭은 남북 방향으로 N, 동서 방향으로 M의 길이를 가진 격자판으로, 울제가 풀밭 밖으로 벗어난 시간이 한 순간이라도 있을 경우 탈영이 되므로 욱제가 풀밭 밖으로 벗어나게 해서는 안된다. 조교가 욱제에게 내릴 수 있는 명령은 1번부터 10번까지 총 10개이다. 명령은 여러 번의 이동으로 이루어져 있다.

욱제의 오리걸음은 북서쪽 끝 격자인 (1, 1)에서 시작한다. 욱제의 오리걸음을 끝내는 유일한 방법은 오리걸음이 시작한 직후나 하나의 명령이 끝난 직후에 남동쪽 끝 격자인 (N, M)에 도착하여 출구를 통해 즉시 도망가는 것이다. 당연히 욱제는 도망갈 기회가 생기면 바로 도망갈 것이다. 조교는 욱제에게 영원히 오리걸음을 시키고 싶지만, 욱제를 영원히 훈련소에 가두는 것은 불법이므로 오리걸음은 유한번의 명령 내로 끝나야 한다. 욱제에게 오리걸음을 시키는 방법의 수를 구해보자. 단, 두 오리걸음이 다르다는 것은 조교의 명령 번호를 순서대로 늘어놓은 수열이 다르다는 것이다.

첫 10개의 줄에 10개의 명령이 순서대로 한 줄에 하나씩 주어진다. 각 명령은 N, S, W, E로 이루어진 문자열이며, 각 문자가 뜻하는 이동을 순서대로 실행하는 명령이다. N은 북쪽, S는 남쪽, W는 서쪽, E는 동쪽으로 한 칸 이동하는 것을 뜻한다.

11번째 줄에 N과 M이 공백으로 구분되어 주어진다.

첫째 줄에 욱제에게 오리걸음을 시키는 방법의 수를 993,244,853으로 나눈 나머지를 출력한다. 욱제에게 오리걸음을 시키는 방법이 무한히 많을 경우 -1을 출력한다.

• 각 명령의 길이는 1 이상 9,316 이하이다.
• 1 ≤ N, M ≤ 1,000