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

Дан неориентированный граф с $$$n$$$ вершинами и $$$m$$$ рёбрами. Каждое ребро соединяет две вершины $$$(u, v)$$$ и каждый день появляется с вероятностью $$$\frac{p}{q}$$$.

Изначально в вершине $$$1$$$ есть сообщение. В конце дня вершина имеет сообщение тогда и только тогда, когда сама она или хотя бы одна из смежных с ней вершин имела сообщение в прошлый день. Обратите внимание, что каждый день ребро выбирает своё появление независимо.

Вычислите математическое ожидание количества дней, прежде чем все вершины получат сообщение, по модулю $$$998\,244\,353$$$.

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1\leq n\leq 21$$$, $$$n-1\leq m\leq\frac{n(n-1)}{2}$$$).

Затем следуют $$$m$$$ строк, каждая из которых содержит четыре целых числа $$$u$$$, $$$v$$$, $$$p$$$ и $$$q$$$ ($$$1\leq u\neq v\leq n$$$, $$$1\leq p<q<998\,244\,353$$$, $$$\gcd(p,q)=1$$$) — существует неориентированное ребро между вершинами $$$u$$$ и $$$v$$$, и оно каждый день появляется с вероятностью $$$\frac{p}{q}$$$.

Гарантируется, что в графе нет петель или кратных рёбер и что граф связен, если все рёбра появились.

Дополнительное ограничение на входные данные: Пусть $$$g_{i,j}$$$ — вероятность появления ребра между вершинами $$$i$$$ и $$$j$$$ ($$$g_{i,j}=0$$$, если между $$$i$$$ и $$$j$$$ нет ребра). Гарантируется, что для любого $$$S\subseteq\{1,2,\ldots,n\}$$$ ($$$|S|\ge 1$$$), $$$$$$ \prod_{i\in S}\left(\prod_{j\in\{1,2,\ldots,n\}\setminus S}(1-g_{i,j})\right)\not\equiv1\pmod{998\,244\,353}. $$$$$$

Выходные данные

Выведите одно целое число в единственной строке вывода — математическое ожидание количества дней, по модулю $$$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}$$$.

Примеры
Входные данные
2 1
1 2 1 10
Выходные данные
10
Входные данные
3 3
1 2 1 2
1 3 1 2
2 3 1 2
Выходные данные
887328316
Входные данные
1 0
Выходные данные
0
Входные данные
5 8
1 2 1 11
1 3 2 11
1 4 3 11
1 5 4 11
2 4 5 11
2 5 6 11
3 4 7 11
4 5 8 11
Выходные данные
469993557
Входные данные
21 22
1 2 3 4
2 3 4 5
3 4 5 6
5 6 7 8
6 7 8 9
7 8 9 10
8 9 2 3
9 10 3 4
10 11 4 5
11 12 5 6
12 13 6 7
13 14 7 8
14 15 8 9
15 16 9 10
16 17 2 3
17 18 3 4
18 19 4 5
19 20 5 6
20 21 6 7
1 10 100 1001
15 4 147 220
4 11 1 998244352
Выходные данные
299529765
Примечание

В первом тесте ответ равен математическому ожиданию количества дней, прежде чем появится единственное ребро в графе, и оно равно $$$\frac{1}{0.1}=10$$$.

Во втором тесте ответ равен $$$\frac{20}{9}$$$, прежде чем он будет взят по модулю $$$998\,244\,353$$$.

В третьем тесте единственная вершина уже имеет сообщение, поэтому ответ равен $$$0$$$.