A Friend's Face and One Blade of Grass

Time limit3sMemory limit1024 MB

Summary

Count the command sequences that take Wookje from (1,1) to (N,M) without leaving the grid, or report -1 if there are infinitely many.

Level: Medium6 of 10
Topics: Graph, Dynamic programming, Topological sort
Solved: No attempts yet

Problem

Wookje pulls up a single blade of grass and rests while picturing a friend's face. The teaching assistant is angry that he rests after pulling only one weed, so the assistant wants to make Wookje do the duck walk.

The lawn is a grid that runs $N$ cells from north to south and $M$ cells from east to west. If Wookje is outside the lawn for even one moment, he deserts, so he must never leave the lawn. The assistant can give 10 commands, numbered 1 to 10. Each command consists of several moves.

The duck walk starts at the northwest corner cell $(1, 1)$ . The only way to end the duck walk is to reach the southeast corner cell $(N, M)$ right after the walk starts or right after a command finishes, and then leave through the exit immediately. Wookje always escapes as soon as he gets the chance.

The assistant wants the duck walk to go on forever, but keeping a trainee in training camp forever is illegal, so the duck walk must end within a finite number of commands. Count the ways to make Wookje do the duck walk. Two duck walks are different if the sequences of command numbers differ.

Input

The first 10 lines contain commands 1 to 10, one per line, in order. Each command is a string of the letters N, S, W, and E, and the moves are executed in order. N moves one cell north, S moves one cell south, W moves one cell west, and E moves one cell east.

The 11th line contains $N$ and $M$ , separated by a space.

Output

Print the number of ways to make Wookje do the duck walk, modulo 993244853, on the first line. If there are infinitely many ways, print -1.

Constraints

Each command has a length of at least 1 and at most 9316.

$1 \le N, M \le 1000$

Examples4

Example 1
Input
```
EWE
E
E
S
S
S
E
ENS
E
S
2 2
```
Expected output
```
44
```
Example 2
Input
```
NW
S
S
S
E
E
E
S
S
S
2 2
```
Expected output
```
36
```
Example 3
Input
```
N
S
W
E
N
S
W
E
N
S
5 5
```
Expected output
```
-1
```
Example 4
Input
```
E
E
E
E
E
E
E
E
E
E
1 10
```
Expected output
```
6755147
```