Nautilus
Nautilus is a secret submarine, sailing around the ocean and trying to remain hidden.
The ocean is modelled as r * c 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 fi gure above right.
Vytautas has constructed a radar that intercepts the periodic submarine signals. Over the last m minutes, the radar has collected m radio signals, represented as a sequence of m 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.
Input
The first line contains three integers *r, c, m (1 ≤ r, c ≤ 500, 1 ≤ m ≤ 5000). The next r lines form an r * c grid of characters "#" and "." representing the ocean map. The last line describes the signals intercepted by Vytautas - a string of m characters, all belonging to the set {N, E, S, W, ?}.
Output
Print a single integer - the number of possible distinct current positions of Nautilus.