H. Тенцинг и случайные вещественные числа
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Имеется $$$n$$$ непрерывно распределённых случайных вещественных чисел от 0 до 1 включительно, которые обозначаются как $$$x_1, x_2, \ldots, x_n$$$.

Тенцинг имеет $$$m$$$ условий. Каждое условие имеет вид $$$x_i+x_j\le 1$$$ или $$$x_i+x_j\ge 1$$$.

Тенцинг хочет узнать вероятность того, что все условия выполнены, по модулю $$$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$$$.

Примеры
Входные данные
3 2
0 1 2
1 3 3
Выходные данные
748683265
Входные данные
3 3
0 1 2
0 1 3
0 2 3
Выходные данные
748683265
Входные данные
3 4
0 1 2
0 1 3
1 2 3
1 2 2
Выходные данные
935854081
Входные данные
4 4
0 1 2
0 3 4
1 1 3
1 2 4
Выходные данные
0
Входные данные
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
Выходные данные
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$$$.