[BalticOI 2019 Day1] 潜艇

**译自 [BalticOI 2019](http://boi2019.eio.ee/tasks/) Day1 T2.** ***[Nautilus](http://boi2019.eio.ee/wp-content/uploads/2019/04/nautilus.en_.pdf)***

有一艘潜艇正在海洋中秘密航行。 海洋是一个 $R \times C$ 的网格，其中 `#` 代表岛屿，`.` 代表水域，潜艇只能在水域中航行。 每分钟，潜艇会发出一个无线电信号，代表潜艇要航行的方向。方向由如下字母表示：北（N），东（E），南（S），西（W）。 现在监听者已经架设了一台拦截潜艇信号的雷达。在最近的 $M$ 分钟，雷达收集到了 $M$ 个信号，由一个长度为 $M$ 的字符串表示，例如 `WS?EE??`。收集到的信号有些无法解码，用 `?` 表示。 监听者并不知道潜艇最初的位置，但想要借助地图计算出潜艇的当前位置。请你帮助监听者计算出潜艇当前可能的位置共有几种。

输入第一行包含三个整数 $R,C,M$。 接下来 $R$ 行，每行 $C$ 个字符，描述海域地图。 最后一行是一个长度为 $M$ 的字符串，代表了监听者监听到的信号。保证字符串中只含有 `N`，`E`，`S`，`W`，`?` 这几种字符。

输出一个整数：潜艇当前可能的位置有几种。

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

22

各子任务的分值与数据规模如下： - 子任务 1（29 分）：$1 \leq R,C,M \leq 100$，监听到的信号中没有 `?`。 - 子任务 2（37 分）：$1 \leq R,C,M \leq 100$。 - 子任务 3（34 分）：$1 \leq R,C \leq 500$，$1 \leq M \leq 5000$。