黑洞 (blackhole)

【题目描述】

小明有一个有 $n$ 行 $m$ 列的棋盘，一共有 $n\times m$ 个棋盘格子。

有一天他的棋盘被黑客入侵了，造出了一个黑洞，位于棋盘的第 $x$ 行，第 $y$ 列，而其他格子都是正常的，而每个格子上都放有一颗棋子。小明想到了一个有趣的游戏，他可以通过倾斜棋盘使得棋子发生一模一样的位移。具体来说，小明可以通过倾斜棋盘，使得棋盘上所有棋子同时往上下左右位移一个格子。

举个例子，当前棋子位于 $(i,j)$ ，小明设计了倾斜棋盘的按钮。

1. 按钮 U：它将移动到 $(i − 1, j)$
2. 按钮 D：它将移动到 $(i + 1, j)$
3. 按钮 L：它将移动到 $(i, j − 1)$
4. 按钮 R：它将移动到 $(i, j + 1)$

如果一颗棋子掉进黑洞里或掉出棋盘，那么该棋子将离开棋盘不再回来。

但黑洞的确切位置不知道。

小明想知道，当他确定了之后的只包含字符U,D,L,R的操作序列，有多少黑洞满足经过上述操作序列后棋盘上剩余棋子数量为 $k$。

【输入格式】

输入包含多个数据。

第一行包含一个整数 $T$，表示数据组数。

对于每组数据， 第一行包含三个整数 $n,m,k$。

第二行包含一个字符串 $s_1s_2 · · · s_l（s_i ∈ \{'U', 'D', 'L', 'R'\}）$。

【输出格式】

对于每个测试用例，输出一个整数。

【样例 $1$ 输入】

2
5 5 3
ULDDRR
5 5 10
UUUUUUU

【样例 $1$ 输出】

1
0

【样例 $2$】

见下发文件

【样例 $3$】

见下发文件

【子任务】

令$n$表示字符串长度

对于$30\%$的数据，$1\le n,m,l\le 10$。

对于$60\%$的数据，$1\le n,m,l\le 100$

对于$100\%$的数据，$T\le 10,1\le n,m\le 1000,1\le l\le 10^5，0\le k\le nm$。