Problem Description

There are $ N $ walls. Each wall can be painted in one of three colors: red, green, or blue.

Given $ M $ conditions. The $ i $-th condition provides integers $ a_i, b_i $ and characters $ x_i, y_i $, which indicate that:

• When wall $ a_i $ is painted in color $ x_i $, wall $ b_i $ must not be painted in color $ y_i $.

Here, $ x_i, y_i $ are each one of the characters R, G, B, where R represents red, G represents green, and B represents blue.

Determine the number of ways to paint the walls that satisfy all $ M $ conditions.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ a_1 $ $ x_1 $ $ b_1 $ $ y_1 $ $\vdots$ $ a_M $ $ x_M $ $ b_M $ $ y_M $

Output Format

Output the answer in one line.

Sample Input and Output

Sample Input #1

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

Sample Output #1

6

Sample Input #2

1 0

Sample Output #2

3

Sample Input #3

22 0

Sample Output #3

31381059609

Sample Input #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

Sample Output #4

13

Notes/Hints

Constraints

• $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 $ are each one of the characters R, G, B.
• For $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 $ are all integers.

Sample Explanation 1

If wall $ 1 $ is painted red, wall $ 2 $ can be painted green or blue. If wall $ 1 $ is painted green, wall $ 2 $ can be painted green or blue. If wall $ 1 $ is painted blue, wall $ 2 $ can be painted red or blue. Therefore, there are a total of $ 6 $ ways to paint the walls.

Sample Explanation 2

Any color can be used to paint wall $ 1 $ to satisfy the conditions.

Sample Explanation 3

Be careful of overflow.

见题面 Input 部分

见题面 Output 部分