G. [Algo Beat Contest 009 & MROI Round 1] Sheepfold

Jonny 是一名唤魔者。与其他唤魔者一样，Jonny 同样热衷于把蓝色的羊变成红色。

这一天，Jonny 潜入了 Steve 的羊圈。Steve 的羊圈可以用一个 的字符矩阵 表示，其中，对于任意 ，若 ，则这个位置有一头红羊；若 ，则这个位置有一头蓝羊；若 ，则这个位置没有羊。

Jonny 可以施展任意次魔法，使任意一头蓝羊变成红羊。对于任意可以通过施展魔法得到的矩阵 ，我们称之为它是原矩阵 的一个变换。注意可以不施展魔法。

对于一个变换，Jonny 认为它是好的，当且仅当在这个变换中任意一行最多仅有一头红羊，且任意一列最多仅有一头蓝羊。

:::info[形式化描述] 对于 的一个变换 ，当且仅当它满足：

此时称 是 的一个好的变换。 :::

现在，Jonny 想知道，对于所有合法的变换，有多少变换是好的。由于答案可能很大，你只需要输出方案数对 取模的结果。

由于矩阵可能很大，本题采用特殊的输入方式。

首先第一行输入两个整数 ，令矩阵 当前全为 .。

第 行，第 行输入两个整数 和一个字符 ，表示将矩阵第 行第 列的字符改为 。行、列下标均从 开始。

一行输出一个数，表示符合条件的方案数，答案对 取模。

输入 #1

6 6
1 1 R
1 4 B
3 5 B
4 3 R
5 3 B
6 5 R

输出 #1

4

输入 #2

2 2
1 1 R
1 2 R

输出 #2

0

输入 #3

2 3
1 2 B
2 1 R
2 2 B

输出 #3

1

【样例 1 解释】

样例中的原始羊圈如图所示。

:::info[展开以查看图片] :::

四种好的变换分别为：

:::info[所有好的变换]

R..B..
......
....B.
..R...
..B...
....R.

R..B..
......
....R.
..R...
..B...
....R.

R..B..
......
....B.
..R...
..R...
....R.

R..B..
......
....R.
..R...
..R...
....R.

:::

如图所示。

:::info[展开以查看图片]

:::

【数据范围】

对于所有数据，保证：

• ，；
• 对于所有 ，，；
• 对于所有 ，。