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

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

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

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

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

Далее следуют $m$ строк, каждая из которых содержит четыре целых числа $u, v, p$ и $q$ ($1 \le u \neq v \le n$, $1 \le 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, \dots, n\}$ ($|S| \ge 1$),

$$\prod_{i \in S} \left( \prod_{j \in \{1, 2, \dots, n\} \setminus S} (1 - g_{i,j}) \right) \not\equiv 1 \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} \pmod{M}$. Другими словами, выведите такое целое число $x$, что $0 \le x < M$ и $x \cdot q \equiv p \pmod{M}$.

Примеры

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

2 1
1 2 1 10

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

10

Примечание

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

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

3 3
1 2 1 2
1 3 1 2
2 3 1 2

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

887328316

Примечание

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

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

1 0

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

0

Примечание

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

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

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

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

469993557

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

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

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

299529765