Имеется \(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}\).
Выходные данные
Выведите вероятность того, что все условия выполнены, по модулю \(M = 998~244~353\).
Примечание
В первом примере условиями являются \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
0 1 2
1 3 3
|
748683265
|
|
2
|
3 3
0 1 2
0 1 3
0 2 3
|
748683265
|
|
3
|
3 4
0 1 2
0 1 3
1 2 3
1 2 2
|
935854081
|
|
4
|
4 4
0 1 2
0 3 4
1 1 3
1 2 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
|
997687297
|