Mirko 在他汽车的后座上发现了一个有 $N$ 行 $M$ 列的矩阵。矩阵的第一行由数字 $1, 2, \dots, M$ 组成，第二行由数字 $M+1, M+2, \dots, 2 \cdot M$ 组成，依此类推，直到第 $N$ 行分别由数字 $(N-1) \cdot M + 1, (N-1) \cdot M + 2, \dots, N \cdot M$ 组成。

例如，当 $N = 3$ 且 $M = 4$ 时：

这样的矩阵对他来说不够有趣，因此他选择了某一行或某一列共 $K$ 次，并将其中的值乘以一个非负整数。

自然地，现在他想知道矩阵中所有数值的和。由于这个和可能会非常大，Mirko 只需要知道该值模 $10^9 + 7$ 的结果即可。请帮助 Mirko 回答这个问题。

输入格式

输入的第一行包含三个整数 $N$（$1 \le N \le 1\,000\,000$）、$M$（$1 \le M \le 1\,000\,000$）和 $K$（$1 \le K \le 1000$）。

接下来的 $K$ 行每行描述一个操作：

• 或者是将第 $X$ 行乘以 $Y$，格式为 R X Y，其中 R 代表行乘法，$X$ 是一个正整数（$1 \le X \le N$），$Y$ 是一个非负整数（$0 \le Y \le 10^9$）。
• 或者是将第 $X$ 列乘以 $Y$，格式为 S X Y，其中 S 代表列乘法，$X$ 是一个正整数（$1 \le X \le M$），$Y$ 是一个非负整数（$0 \le Y \le 10^9$）。

输出格式

输出最终矩阵中所有元素的和模 $10^9 + 7$ 的值。

子任务

对于占总分 50 分的测试数据，满足 $1 \le N, M \le 1000$。

样例

输入样例 1

3 4 4
R 2 4
S 4 1
R 3 2
R 2 0

输出样例 1

94

输入样例 2

3 1 1
S 1 4

输出样例 2

24

输入样例 3

2 4 4
S 2 0
S 2 3
R 1 5
S 1 3

输出样例 3

80

说明

样例 1 说明：

在将第二行乘以 4，第四列乘以 1，第三行乘以 2，以及再次将第二行乘以 0 之后，最终的矩阵如下所示：

最终矩阵中元素的和为 $1 + 2 + 3 + 4 + 0 + 0 + 0 + 0 + 18 + 20 + 22 + 24 = 94$。