题目描述

cz_?? 同学凭借未来 IOI 金牌的水平和高超的撩妹技术成功进入 IX 班。但很快 cz_?? 发现他的撩妹技术将可能一无是处，因为军训的队伍由教官指定，而不是让同学任意排列。为了队伍的整齐，教官将IX班所有的学生排成为 $n$ 行 $m$ 列的方阵，且每方阵中每一位学生的身高严格小于他左侧和前方相邻的同学的身高。就是说，设在第 $i$ 行 $j$ 列的同学的身高为 $h{i,j}$，那么有当 $i>1$ 时有 $h{i,j}<h{i-1,j}$，当 $j>1$ 时有 $h{i,j}<h_{i,j-1}$。

cz_?? 知道自己的身高是 $H_1$，并且目测出了其他同学的身高 $H_i$。由于他不能愉快地和妹子玩耍，便假定教官在任意一种合法的方案中等概率选择一种，尝试计算自己相邻的妹子数量的期望，以打发时间。

cz_?? 认为第 $x_1$ 行第 $y_1$ 列和第 $x_2$ 行第 $y_2$ 列相邻，当且仅当 $|x_1-x_2 |+|y_1-y_2 |=1$，同时他认为两个合法的站队方案不同当且仅当存在至少一个人在两种站队方案中所站的位置不同。

cz_?? 觉得这个问题过于无（沙）聊（雕），于是把这个问题扔给了你，由于他不喜欢浮点数，但是他知道答案一定是一个有理数，假定它的既约分数形式是 $\frac{p}{q}$，他希望你输出一个最小非负整数 $c$，使得 $c\times q\equiv p \pmod{10^9 + 7}$。可以证明这样的一个整数必然存在且唯一。

输入格式

第一行包含 $2$ 个正整数 $n,m$ 和 $1$ 个浮点数 $H_1$。
接下来有 $(n\times m-1)$ 行，第 $i$ 行包含 $1$ 个浮点数 $H_i$ 和 $1$ 个字符 $G_i$，如果是 B，表示这名学生是男生，如果是 G 表示这名学生是女生。

输出格式

仅一个整数 $c$。

样例 1

input

2 2 175.20
144.35 B
177.46 G
123.25 B

output

1

样例 2

input

2 2 111.20
144.35 B
177.46 G
123.25 B

output

0

cz_?? 必须站在第 $2$ 行第 $2$ 列，班里唯一的妹子必须站在第 $1$ 行第 $1$ 列。

样例 3

input

2 3 184.72
115.46 B
126.49 G
112.76 B
177.1 B
107.41 G

output

600000005

数据范围与提示

本题目采用子任务式测试，要通过一个子任务中所有通过测试点才能得到该子任务的分数。

对于所有数据均满足 $1\leq n,m\leq 19,n+m\leq 20,100.00\leq H_i\leq 200.00,G_i\in \left{\text{B,G}\right}$，任意两个同学的身高均不相同，输入的浮点数至多保留 $2$ 位小数。

（题目并不难）
（cz_??这个人物纯属虚构，请不要对号入座）