国王宫殿的大厅里有 $N$ 面墙，编号为 $1$ 到 $N$。国王要求皇家画师将每面墙涂成三种颜色之一（红色、绿色或蓝色）。此外，国王还下达了 $M$ 条指令。

每条指令的形式如下：给定两面墙 $a_i$ 和 $b_i$，以及两种颜色 $x_i$ 和 $y_i$。该指令规定，如果墙 $a_i$ 被涂成颜色 $x_i$ 且墙 $b_i$ 被涂成颜色 $y_i$，则皇家画师必须被处决。

你的任务是计算出有多少种涂墙方案，使得皇家画师不会被处决。

输入格式

第一行包含两个整数 $N$ 和 $M$ ($1 \le N \le 22, 1 \le M \le 9 \cdot N \cdot (N - 1)/2$)，分别表示墙的数量和指令的数量。

接下来的 $M$ 行，每行描述一条国王的指令，包含一个整数 $a_i$、一个字母 $x_i$、一个整数 $b_i$ 和一个字母 $y_i$，中间用空格隔开（$1 \le a_i < b_i \le N$，$x_i$ 和 $y_i$ 分别为代表红色、绿色和蓝色的字母 'R'、'G' 和 'B'）。你可以假设所有 $M$ 条指令都是两两不同的（没有两条指令的效果完全相同）。

输出格式

输出一个整数：使得皇家画师不会被处决的涂墙方案数。

样例

样例输入 1

2 3
1 R 2 R
1 G 2 R
1 B 2 G

样例输出 1

6

样例输入 2

1 0

样例输出 2

3

样例输入 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