题目描述

不高兴找到了一个 $N$ 行 $M$ 列的矩阵。矩阵的第一行数字为 $1,\ 2,\ 3,\ \ldots,\ M$ ，第二行数字为 $M+1,\ M+2,\ \ldots,\ 2 \times M,\ldots$ 第$N$行数字为 $(N-1) \times M+1,\ (N-1) \times M+2,\ \ldots,\ N \times M$ 。

例如，对于 $N=3,\ M=4$：

当然这样的矩阵是无趣的，所有他选择了其中一行或一列，将其乘以非负数，会进行 $K$ 次。最后他想知道矩阵中所有值的总和。由于总和可能会很大，需要总和模 $10^9+7$.

输入格式

第一行三个正整数 $N，M，K$ 。

以下 $K$ 行中的每一行有两种描述：

"R X Y"，$R$ 表示行，即将第 $X(1 \leq X \leq N)$ 行的所有数乘以 $Y$ 。

"S X Y"，S表示列，即将第 $X(1 \leq X \leq M)$ 列的所有数乘以 $Y$ 。

输出格式

输出矩阵所有数的和，并模 $10^9+7$ .

样例1输入

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

样例1输出

94

样例1解释

将第二行与 $4$ 相乘后，第四列乘 $1$，第三行乘 $2$，第二行乘 $0$，最终矩阵如下所示：

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

数据范围

• 对于 $50$% 的数据， $1 \leq N,M \leq 1000$ 。

• 对于 $100$% 的数据， $1 \leq N,M \leq 1000000,\ 1 \leq K \leq 1000,\ 0 \leq X,\ Y \leq 10^9$ 。

大样例下载

百度网盘大样例下载 提取码: GFOI

阿里云盘大样例下载

夸克云盘大样例下载