You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

译自 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$。