题目描述

给定一个 $H$ 行 $W$ 列的网格。

网格的每个格子是陆地或海洋，由 $H$ 个长度为 $W$ 的字符串 $S_1, S_2, \dots, S_H$ 表示。记从上往下数第 $i$ 行、从左往右数第 $j$ 列的格子为 $(i, j)$。如果 $S_i$ 的第 $j$ 个字符是 .，则 $(i, j)$ 是陆地；如果该字符是 #，则 $(i, j)$ 是海洋。

数据保证网格周边的所有格子（即满足 $i=1$、$i=H$、$j=1$ 或 $j=W$ 至少一个条件的格子 $(i, j)$）都是海洋。

高桥君的飞船坠毁在网格的某个格子上。之后，他根据一个长度为 $N$ 且由 L、R、U、D 组成的指令字符串 $T$ 在网格上移动了 $N$ 次。对于 $i=1, 2, \dots, 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$。

第二行包含一个长度为 $N$ 的字符串 $T$。

接下来 $H$ 行，每行包含一个长度为 $W$ 的字符串 $S_i$ —— 表示网格的状态。

输出格式

输出一行，一个整数，表示高桥君当前可能所在的格子数量。

样例输入 1

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

样例输出 1

2

样例输入 2

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

样例输出 2

6

说明

样例解释

在第一个样例中，可能有以下两种情况，因此共有两个格子可能是高桥君的当前位置：$(3, 4)$ 和 $(4, 5)$。

• 他坠毁在格子 $(3, 5)$ 并依次移动：$(3, 5) \to (3, 4) \to (2, 4) \to (2, 3) \to (3, 3) \to (3, 4)$。
• 他坠毁在格子 $(4, 6)$ 并依次移动：$(4, 6) \to (4, 5) \to (3, 5) \to (3, 4) \to (4, 4) \to (4, 5)$。

数据范围

对于所有测试点，保证 :

• $3 \le H, W \le 500$。
• $1 \le N \le 500$。
• $T$ 是一个长度为 $N$ 且仅由 L, R, U, D 组成的字符串。
• $S_i$ 是一个长度为 $W$ 且仅由 . 和 # 组成的字符串。
• 至少存在一个可能的当前位置。
• 网格周边的所有格子均为海洋（#）。
• 所有的 $H, W, N$ 均为整数。