题目描述

“Philip Industries” 公司正在为新的火星车机器人开发程序。机器人工作的火星区域是一个 $n\times n$ 的正方形网格，每个格子大小为 $1\times 1$，其中有些格子可能有岩石。

数据范围中 $1\le n\le 1000$，有岩石的格子不超过 $300$ 个。

坐标系定义为：格子坐标为

机器人的程序是一串指令，每条指令由一个拉丁字母表示：

• U：从 $(x,y)$ 移动到 $(x,y+1)$；
• D：从 $(x,y)$ 移动到 $(x,y-1)$；
• R：从 $(x,y)$ 移动到 $(x+1,y)$；
• L：从 $(x,y)$ 移动到 $(x-1,y)$。

为了节省存储，工程师只把一串指令 $s$ 存入机器人内存，指令编号为 $1$ 到 $t$。之后可以让机器人执行某个子程序，即一段连续指令。一个子程序由两个整数 $(l,r)$ 描述，表示执行 $s_l,s_{l+1},\ldots,s_r$。

实验中，机器人被放在测试场地的某个初始格子。若机器人依次执行子程序 $(l,r)$ 的指令过程中，既不离开网格，也不走到有岩石的格子上，则称该子程序是正确的。

请根据场地、程序和初始位置，计算该程序有多少个正确子程序。

输入格式

第一行包含两个整数 $n,t$，表示网格大小和指令数。

第二行包含长度为 $t$ 的字符串 $s$，只由 U、D、R、L 组成。

接下来 $n$ 行，每行包含 $n$ 个字符，表示场地：

• . 表示空格；
• # 表示岩石；
• @ 表示机器人初始位置。

坐标轴 $X$ 从左到右，$Y$ 从下到上。保证 @ 恰好出现一次，# 不超过 $300$ 次。

数据范围：

• $1 \le n \le 1000$；
• $1 \le t \le 100000$。

输出格式

输出一个整数，表示正确子程序的数量。

样例输入

4 4
ULUR
..#.
....
.#@.
#.#.

样例输出

6

样例解释

样例中正确的子程序为：

• $(1,1)=\texttt{U}$；
• $(1,2)=\texttt{UL}$；
• $(1,3)=\texttt{ULU}$；
• $(3,3)=\texttt{U}$；
• $(3,4)=\texttt{UR}$；
• $(4,4)=\texttt{R}$。