题目描述

给定一个 $N$ 行 $M$ 列的网格。现有两名玩家，他们需要分别选择一个格子作为初始位置，且两人的初始位置不能相同。另有一个操作序列 $S$，其中每个操作都是以下四种之一：

• U：向上移动一格；
• D：向下移动一格；
• L：向左移动一格；
• R：向右移动一格。

两名玩家会按照该操作序列 $S$ 同时移动。对于序列中的每一个操作，两名玩家都同时尝试沿对应方向移动一格。若某名玩家在该方向上移出网格边界，则这一步他将停留在原位置不动。

现在，你需要计算，有多少种不同的初始位置对，能够使得两人在执行完整个操作序列后，最终位于同一个格子。

特别地，初始位置对视为有序对：若两人的初始位置分别为 $(r_1, c_1)$ 和 $(r_2, c_2)$，那么 $((r_1, c_1), (r_2, c_2))$ 与 $((r_2, c_2), (r_1, c_1))$ 视为两种不同的方案。

输入格式

输入共两行。

第一行包含两个整数 $N, M$。

第二行包含一个字符串 $S$，表示操作序列。

输出格式

输出一个整数，表示满足条件的初始位置对数量。

10 9
UULDURRRDLDLDD

284

提示

【评测用例规模与约定】

• 对于 $30\%$ 的评测用例，$N, M \le 50$，$|S| \le 1000$；
• 对于所有的评测用例，$N, M \le 5000$，$1 \le |S| \le 10^6$。