问题描述

有一个 $H$ 行 $W$ 列的网格。

网格中的每个单元格都是陆地或海洋，用长度为 $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$ 中至少一个的单元格）都是海洋。

高桥的飞船在网格中的一个单元格上坠毁。之后，他按照长度为 $N$ 的字符串 $T$ 中的指令移动了 $N$ 次。对于 $i = 1, 2, \ldots, N$，$T$ 的第 $i$ 个字符描述了第 $i$ 次移动的方向如下：

• L 表示向左移动一个单元格。也就是说，如果他在移动前在 $(i, j)$，移动后会在 $(i, j - 1)$。
• R 表示向右移动一个单元格。也就是说，如果他在移动前在 $(i, j)$，移动后会在 $(i, j + 1)$。
• U 表示向上移动一个单元格。也就是说，如果他在移动前在 $(i, j)$，移动后会在 $(i - 1, j)$。
• D 表示向下移动一个单元格。也就是说，如果他在移动前在 $(i, j)$，移动后会在 $(i + 1, j)$。

已知他路径上的所有单元格（包括他坠毁的单元格和他当前所在的单元格）都不是海洋。请输出可能是他当前位置的单元格数量。

约束条件

• $H, W$ 和 $N$ 为整数。
• $3 \leq H, W \leq 500$
• $1 \leq N \leq 500$
• $T$ 是长度为 $N$ 的字符串，由 L、R、U 和 D 组成。
• $S_i$ 是长度为 $W$ 的字符串，由 . 和 # 组成。
• 至少有一个单元格可能是高桥的当前位置。
• 网格周边的所有单元格都是海洋。

输入

输入以以下格式从标准输入给出：

$H$ $W$ $N$

$T$

$S_1$

$S_2$

$\vdots$

$S_H$

输出

一个整数，表示可能的方案数

样例

6 7 5
LULDR
#######
#...#.#
##...##
#.#...#
#...#.#
#######

2

13 16 9
ULURDLURD
################
##..##.#..####.#
###.#..#.....#.#
#..##..#####.###
#...#..#......##
###.##.#..#....#
##.#####....##.#
###.###.#.#.#..#
######.....##..#
#...#.#.######.#
##..###..#..#.##
#...#.#.#...#..#
################

6