题目背景

译自 BalticOI 2019 Day1 T2. Nautilus

题目描述

有一艘潜艇正在海洋中秘密航行。

海洋是一个 $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$。