Description

A submarine is secretly traveling in the ocean.

The ocean is an $R \times C$ grid, where # represents an island and . represents water. The submarine can travel only in water.

Every minute, the submarine sends a radio signal that indicates the direction it will move. Directions are represented by the following letters: North (N), East (E), South (S), West (W).

Now the eavesdropper has set up a radar to intercept the submarine’s signals. During the last $M$ minutes, the radar collected $M$ signals, represented by a string of length $M$, for example WS?EE??. Some collected signals cannot be decoded and are represented by ?.

The eavesdropper does not know the submarine’s initial position, but wants to use the map to determine the submarine’s current position. Please help compute how many possible current positions the submarine may be in.

Input Format

The first line contains three integers $R, C, M$.

The next $R$ lines each contain $C$ characters describing the sea map.

The last line is a string of length $M$, representing the intercepted signals. It is guaranteed that the string contains only N, E, S, W, ?.

Output Format

Output one integer: the number of possible current positions of the submarine.

5 9 7
...##....
..#.##..#
..#....##
.##...#..
....#....
WS?EE??

22

Hint

The scores and Constraints for each subtask are as follows:

• Subtask 1 (29 points): $1 \leq R, C, M \leq 100$, and there is no ? in the intercepted signals.
• Subtask 2 (37 points): $1 \leq R, C, M \leq 100$.
• Subtask 3 (34 points): $1 \leq R, C \leq 500$, $1 \leq M \leq 5000$.

Translated by ChatGPT 5