存在 $$$n$$$ 0 到 1 之间的均匀随机实变量(含 0 和 1),分别表示为 $$$x_1, x_2, \ldots, x_n$$$。
丹增有 $$$m$$$ 条件。每个条件的形式为 $$$x_i+x_j\le 1$$$ 或 $$$x_i+x_j\ge 1$$$。
Tenzing 想知道满足所有条件的概率,以 $$$998~244~353$$$ 为模。
正式地,令 $$$M = 998~244~353$$$。可以证明,答案可以表示为不可约分数 $$$\frac{p}{q}$$$,其中 $$$p$$$ 和 $$$q$$$ 是整数,$$$q \not \equiv 0 \pmod{M}$$$。输出等于 $$$p \cdot q^{-1} \bmod M$$$ 的整数。换句话说,输出整数$$$x$$$,$$$0 \le x < M$$$ 和$$$x \cdot q \equiv p \pmod{M}$$$。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1\le n\le 20$$$, $$$0\le m\le n^2+n$$$)。
接下来的 $$$m$$$ 输入行包含三个整数 $$$t$$$、$$$i$$$ 和 $$$j$$$ ($$$t \in \{0,1\}$$$, $$$1\le i\le j\le n$$$)。
- 如果 $$$t=0$$$,则条件为 $$$x_i+x_j\le 1$$$。
- 如果 $$$t=1$$$,则条件为 $$$x_i+x_j\ge 1$$$。
保证所有条件都是成对不同的。
输出
输出满足所有条件的概率,模 $$$M = 998~244~353$$$。
示例
输入 #1
3 2 0 1 2 1 3 3
输出 #1
748683265
输入 #2
3 3 0 1 2 0 1 3 0 2 3
输出 #2
748683265
输入 #3
3 4 0 1 2 0 1 3 1 2 3 1 2 2
输出 #3
935854081
输入#4
4 4 0 1 2 0 3 4 1 1 3 1 2 4
输出#4
0
输入 #5
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
输出 #5
997687297
注意
在第一个测试用例中,条件为 $$$x_1+x_2 \le 1$$$ 和 $$$x_3+x_3\ge 1$$$,满足每个条件的概率为 $$$\frac 12$$$,因此它们都满足的概率为 $$$\frac 12\cdot \frac 12=\frac 14$$$,模$$$998~244~353$$$ 等于 $$$748683265$$$。
在第二个测试用例中,答案是 $$$\frac 14$$$。
在第三个测试用例中,答案是 $$$\frac 1{16}$$$。
在第四个测试用例中,所有变量的总和必须等于 $$$2$$$,因此概率为 $$$0$$$。