시간 제한메모리 제한제출정답맞힌 사람정답 비율
6 초 1024 MB41241750.000%

문제

There are $N$ walls in the hall of the King's palace, numbered by integers from $1$ to $N$. The King asks the Royal Painter to paint each wall in one of three colors (red, green, or blue). Additionally, the King gives $M$ orders.

Every order has the following form: given two walls, $a_i$ and $b_i$, and two colors, $x_i$ and $y_i$, the order dictates that, if the wall $a_i$ is painted with color $x_i$ and the wall $b_i$ is painted with color $y_i$, the Royal Painter has to be executed.

Your task is to find a number of ways to paint the walls so that the Royal Painter will not be executed.

입력

The first line of the input contains two integers $N$ and $M$ ($1 \le N \le 22$, $1 \le M \le 9 \cdot N \cdot (N-1)/2$): the number of walls and the number of orders, respectively.

Each of the following $M$ lines describes one King's order and contains an integer $a_i$, a letter $x_i$, an integer $b_i$, and a letter $y_i$, separated by single spaces ($1 \le a_i < b_i \le N$, $x_i$ and $y_i$ are letters from 'R', 'G', and 'B', denoting the red, green, and blue colors, respectively). You may assume that all $M$ orders are pairwise distinct (no two orders have the exact same effect).

출력

Print one integer: the number of ways to paint the walls so that the Royal Painter will not be executed.

예제 입력 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