AT_abc341_c [ABC341C] Takahashi Gets Lost

有一个 $H$ 行 $W$ 列的网格。 网格中的每个格子要么是**陆地**，要么是**海洋**，这些信息由 $H$ 个长度为 $W$ 的字符串 $S_1,\ S_2,\ \ldots,\ S_H$ 给出。用 $(i,\ j)$ 表示从上到下第 $i$ 行、从左到右第 $j$ 列的格子，当 $S_i$ 的第 $j$ 个字符为 `.` 时，格子 $(i,\ j)$ 是陆地；为 `#` 时，格子 $(i,\ j)$ 是海洋。 这里保证网格的外周格子（即满足 $i=1$、$i=H$、$j=1$、$j=W$ 中至少一个条件的格子 $(i,\ j)$）全部都是海洋。 高桥君乘坐的宇宙飞船在网格上的某个格子紧急降落。之后，高桥君按照只包含 `L`、`R`、`U`、`D` 的长度为 $N$ 的字符串 $T$ 所描述的操作，在网格上移动了 $N$ 次。对于 $i=1,2,\ldots,N$，$T$ 的第 $i$ 个字符表示第 $i$ 次移动的内容，具体如下： - `L` 表示向左移动 $1$ 格。即，若移动前在 $(i, j)$，则移动后在 $(i, j-1)$。 - `R` 表示向右移动 $1$ 格。即，若移动前在 $(i, j)$，则移动后在 $(i, j+1)$。 - `U` 表示向上移动 $1$ 格。即，若移动前在 $(i, j)$，则移动后在 $(i-1, j)$。 - `D` 表示向下移动 $1$ 格。即，若移动前在 $(i, j)$，则移动后在 $(i+1, j)$。 已知高桥君移动路径上的所有格子（包括降落点和当前所在格子）都不是海洋。请输出高桥君当前可能所在的格子的个数。

输入按以下格式从标准输入中给出。 > $H$ $W$ $N$ > $T$ > $S_1$ > $S_2$ > $\vdots$ > $S_H$

请输出答案。

### 限制条件 - $H,\ W,\ N$ 为整数。 - $3 \leq H,\ W \leq 500$。 - $1 \leq N \leq 500$。 - $T$ 是只包含 `L`、`R`、`U`、`D` 的长度为 $N$ 的字符串。 - $S_i$ 是只包含 `.` 和 `#` 的长度为 $W$ 的字符串。 - 至少存在 $1$ 个格子可能是高桥君当前所在的位置。 - 网格的外周格子全部是海洋。 ### 样例解释 1 由于存在以下两种情况，高桥君当前可能所在的格子为 $(3,4)$ 和 $(4,5)$，共 $2$ 个。 - 在 $(3,5)$ 降落，移动路径为 $(3,5) \rightarrow (3,4) \rightarrow (2,4) \rightarrow (2,3) \rightarrow (3,3) \rightarrow (3,4)$。 - 在 $(4,6)$ 降落，移动路径为 $(4,6) \rightarrow (4,5) \rightarrow (3,5) \rightarrow (3,4) \rightarrow (4,4) \rightarrow (4,5)$。 由 ChatGPT 4.1 翻译