Nautilus 是一艘秘密潜艇，在海洋中航行并试图保持隐蔽。
海洋被建模为一个 $R \times C$ 的网格，其中 “#” 代表岛屿，“.” 代表水域。例如：
...##.... ..#.##..# ..#....## .##...#.. ....#....
每一分钟，Nautilus 都会发出一个无线电信号，揭示潜艇即将采取的方向。方向总是以下之一：北 (N)、东 (E)、南 (S)、西 (W)，如右上方的图所示。
Vytautas 建造了一个雷达来拦截周期性的潜艇信号。在过去的 $M$ 分钟里，雷达收集了 $M$ 个无线电信号，表示为一个包含 $M$ 个字符的序列，例如 “WS?EE??”。有些信号无法解码，这些信号被标记为 “?”。
Vytautas 不知道潜艇的初始位置，但想利用海洋地图来确定其当前位置。已知 Nautilus 始终停留在地图上的水域单元格中，请帮助 Vytautas 计算 Nautilus 当前可能位于的互不相同的单元格数量。
输入格式
第一行包含三个整数 $R, C, M$。
接下来的 $R$ 行构成一个 $R \times C$ 的网格，包含字符 “#” 和 “.”，表示海洋地图。
最后一行描述了 Vytautas 拦截到的信号 —— 一个长度为 $M$ 的字符串，所有字符均属于集合 $\{N, E, S, W, ?\}$。
输出格式
输出一个整数：Nautilus 当前可能位于的互不相同的单元格数量。
样例
输入 1
5 9 7 ...##.... ..#.##..# ..#....## .##...#.. ....#.... WS?EE??
输出 1
22
子任务
测试点满足以下条件：
- (29 分) $1 \le R, C, M \le 100$；没有 “?” 符号。
- (37 分) $1 \le R, C, M \le 100$。
- (34 分) $1 \le R, C \le 500$；$1 \le M \le 5\,000$。