Tenzing and Random Real Numbers

Description:

Input:

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n\le 20$$$, $$$0\le m\le n^2+n$$$).

Then following $$$m$$$ lines of input contains three integers $$$t$$$, $$$i$$$ and $$$j$$$ ($$$t \in \{0,1\}$$$, $$$1\le i\le j\le n$$$).

• If $$$t=0$$$, the condition is $$$x_i+x_j\le 1$$$.
• If $$$t=1$$$, the condition is $$$x_i+x_j\ge 1$$$.

It is guaranteed that all conditions are pairwise distinct.

Output:

Output the probability that all the conditions are satisfied, modulo $$$M = 998~244~353$$$.

Sample Input:

3 2
0 1 2
1 3 3

Sample Output:

748683265

Sample Input:

3 3
0 1 2
0 1 3
0 2 3

Sample Output:

748683265

Sample Input:

3 4
0 1 2
0 1 3
1 2 3
1 2 2

Sample Output:

935854081

Sample Input:

4 4
0 1 2
0 3 4
1 1 3
1 2 4

Sample Output:

0

Sample Input:

8 12
0 1 2
0 2 3
1 3 4
0 1 4
0 5 6
0 6 7
1 7 8
0 5 8
1 3 7
1 3 8
1 4 7
1 4 8

Sample Output:

997687297

Note:

In the first test case, the conditions are $$$x_1+x_2 \le 1$$$ and $$$x_3+x_3\ge 1$$$, and the probability that each condition is satisfied is $$$\frac 12$$$, so the probability that they are both satisfied is $$$\frac 12\cdot \frac 12=\frac 14$$$, modulo $$$998~244~353$$$ is equal to $$$748683265$$$.

In the second test case, the answer is $$$\frac 14$$$.

In the third test case, the answer is $$$\frac 1{16}$$$.

In the fourth test case, the sum of all variables must equal $$$2$$$, so the probability is $$$0$$$.