Nautilus#9620
Nautilus is a secret submarine, sailing around the ocean and trying to remain hidden.
The ocean is modelled as by grid of cells, where "#" represents islands and "." represents water. For example:
Every minute, Nautilus emits a radio signal that can reveal the direction the submarine is about to take. The direction is always one of the following: North (N), East (E), South (S), West (W), as shown on the figure above right.
Vytautas has constructed a radar that intercepts the periodic submarine signals. Over the last minutes, the radar has collected radio signals, represented as a sequence of characters, for example "WS?EE??". Some of the signals could not be decoded, these are marked as "?".
Vytautas does not know the initial submarine location, but wants to use the ocean map in order to identify its current location. Given that Nautilus always stays in water cells on the map, help Vytautas calculate the number of distinct cells where Nautilus may be located at currently.
The first line contains three integers , , (1 \leq r, c \leq 500, 1 \leq m \leq 5000). The next lines form an by grid of characters "#" and "." representing the ocean map. The last line describes the signals intercepted by Vytautas - a string of characters, all belonging to the set {N, E, S, W, ?}.
Print a single integer - the number of possible distinct current positions of Nautilus.
Example 1