Baltic Olympiad in Informatics: 2019 Day 1, Problem 2

Nautilus is a secret submarine, sailing around the ocean and trying to remain hidden. The ocean is modelled as an ~R \times 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 figure 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 Specification

The first line of the input contains three integers ~R~, ~C~, ~M~. The next ~R~ lines form an ~R \times C~ grid of characters # and . representing the ocean map. The last line of the input describes the signals intercepted by Vytautas — a string of ~M~ characters, all belonging to the set {N,E,S,W,?}.

Output Specification

Output a single integer: the number of possible distinct current positions of Nautilus.

Sample Input

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

Sample Output

22

Grading

The test groups satisfy the following conditions:

1. (~29~ points) ~1 \le R, C, M \le 100~; there are no ? symbols.
2. (~37~ points) ~1 \le R, C, M \le 100~.
3. (~34~ points) ~1 \le R, C \le 500~; ~1 \le M \le 5\,000~.