U274480 传送

## devout是一个喜欢传送门的女孩纸

现有一个 $n∗m$ 的矩阵，其中有一个位置为传送门，其他位置均为xyc。xyc们想通过跳进传送门或者跳出边界的方式来进入新的世界。 每次操作，全体xyc可以一同向某个方向跳一步（已经进入新世界的xyc除外）。 现在已知操作序列 $S$ 和进入新世界的xyc数量 $k$ ，问传送门可能的位置有多少个？

第一行三个正整数 $n,m,k$ ，如题目描述所示。 第二行一个只含 $U,D,L,R$ 的字符串 $S$ ，表示操作序列。 其中 $U,D,L,R$ 分别表示 上，下，左，右。

一行一个非负整数，表示传送门可能的位置有多少个。

**样例解释** 符合要求的传送门坐标为 $(1,1)$ , $(1,3)$ , $(2,1)$ , $(2,4)$ , $(3,1)$ , $(3,4)$ 。 **数据范围** 对于 $20 \%$ 的数据，满足 $n,m \le 50$ 。 对于 $40 \%$ 的数据，满足 $n,m \le 200$ 。 对于另外 $30 \%$ 的数据，满足只有 $L,R$ 操作。 对于 $100 \%$ 的数据，满足 $n,m \le 1000$ , $k < n∗m$ , $∣S∣\le n∗m$ 。