問題文

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 はいずれも整数

入力例 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