配点 : 400 点
問題文
N 墙。将每面墙涂成红色、绿色或蓝色 1 考虑用颜色绘画。 给出了
M 条件。 第i 个条件是整数 a_i,b_i 和字符 x_i,y_i ,
- 壁 a_i 颜色 当涂上 x_i 时,墙壁 请勿使用 b_i 颜色 当涂上 y_i 进行绘画
。然而, x_i,y_i 是一个字符 R , G , B ,以及 R 当红色时,G 当绿色时, B 代表蓝色。
M 请告诉我有多少种方法来绘制满足所有条件的颜色。
制約
- 1 \leq N \leq 22
- 0 \leq M \leq 9 \times \frac{N(N-1)}{2}
- 1 \leq a_i < b_i \leq N
- x_i,y_i 是一个字符
R,G,B。 - i \neq j 时,(a_i,x_i,b_i,y_i) \neq (a_j,x_j,b_j,y_j)
- N,M,a_i,b_i 均为整数 当把
入力
输入将以以下格式从标准输入给出。
N M a_1 x_1 b_1 y_1 \vdots a_M x_M b_M y_M
出力
答案 打印除以 1 按行输出。
入力例 1
2 3 1 R 2 R 1 G 2 R 1 B 2 G
出力例 1
6
壁 1 涂成红色时,墙壁 2 可以涂成绿色或蓝色。 当把
壁 1 涂成绿色时,墙壁 当用蓝色绘制 2 可以涂成绿色或蓝色。 当把
壁 1 时,墙壁 2 可以涂成红色或蓝色。 因此,总共 6 绘画有不同的方法。 使用任何颜色绘制
入力例 2
1 0
出力例 2
3
壁 1 即可满足条件。
入力例 3
22 0
出力例 3
31381059609
小心溢出。
入力例 4
4 12 2 R 3 R 1 B 2 B 2 R 3 B 3 R 4 R 1 B 4 G 1 R 3 B 3 G 4 B 2 G 3 G 1 B 2 R 1 G 2 R 1 R 3 G 1 G 3 B
出力例 4
13