풀 한 포기 친구 얼굴

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

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

욱제의 오리걸음은 북서쪽 끝 격자인 $(1, 1)$에서 시작한다. 오리걸음을 끝내는 유일한 방법은 오리걸음이 시작한 직후나 명령 하나가 끝난 직후에 남동쪽 끝 격자인 $(N, M)$에 도착해 출구로 즉시 도망가는 것이다. 욱제는 도망갈 기회가 생기면 바로 도망친다.

조교는 욱제에게 영원히 오리걸음을 시키고 싶어 하지만, 욱제를 영원히 훈련소에 가두는 것은 불법이므로 오리걸음은 유한번의 명령 내로 끝나야 한다. 욱제에게 오리걸음을 시키는 방법의 수를 구하라. 두 오리걸음이 다르다는 것은 조교가 내린 명령 번호를 순서대로 늘어놓은 수열이 다르다는 뜻이다.

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

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

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

각 명령의 길이는 1 이상 9316 이하이다.

$1 \le N, M \le 1000$