Dany jest graf nieskierowany o $n$ wierzchołkach i $m$ krawędziach. Każda krawędź łączy dwa wierzchołki $(u, v)$ i ma prawdopodobieństwo $\frac{p}{q}$ pojawienia się każdego dnia.

Początkowo wierzchołek 1 posiada wiadomość. Pod koniec dnia wierzchołek posiada wiadomość wtedy i tylko wtedy, gdy on sam lub co najmniej jeden z jego sąsiadów posiadał wiadomość dzień wcześniej. Zauważ, że każdego dnia każda krawędź wybiera swoją obecność niezależnie.

Oblicz oczekiwaną liczbę dni, zanim wszystkie wierzchołki otrzymają wiadomość, modulo $998\,244\,353$.

Wejście

Pierwsza linia zawiera dwie liczby całkowite $n$ oraz $m$ ($1 \le n \le 21$, $n - 1 \le m \le \frac{n(n-1)}{2}$).

Następnie następuje $m$ linii, z których każda zawiera cztery liczby całkowite $u, v, p$ oraz $q$ ($1 \le u \neq v \le n$, $1 \le p < q < 998\,244\,353$, $\gcd(p, q) = 1$) — istnieje krawędź nieskierowana między $u$ oraz $v$, która ma prawdopodobieństwo pojawienia się $\frac{p}{q}$ każdego dnia.

Gwarantuje się, że w grafie nie ma pętli własnych ani krawędzi wielokrotnych oraz że graf jest spójny, jeśli wszystkie krawędzie są obecne.

Dodatkowy warunek w danych wejściowych: Niech $g_{i,j}$ będzie prawdopodobieństwem pojawienia się krawędzi między $i$ oraz $j$ ($g_{i,j} = 0$, jeśli nie ma krawędzi między $i$ oraz $j$). Gwarantuje się, że dla każdego $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}$$

Wyjście

Wypisz pojedynczą liczbę całkowitą w jedynej linii wyjścia — oczekiwaną liczbę dni, modulo $998\,244\,353$.

Formalnie, niech $M = 998\,244\,353$. Można wykazać, że dokładny wynik można wyrazić jako ułamek nieskracalny $\frac{p}{q}$, gdzie $p$ i $q$ są liczbami całkowitymi oraz $q \not\equiv 0 \pmod{M}$. Wypisz liczbę całkowitą równą $p \cdot q^{-1} \pmod{M}$. Innymi słowy, wypisz taką liczbę całkowitą $x$, że $0 \le x < M$ oraz $x \cdot q \equiv p \pmod{M}$.

Przykład

Przykład 1

2 1
1 2 1 10

Wyjście 1

10

Przykład 2

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

Wyjście 2

887328316

Przykład 3

1 0

Wyjście 3

0

Przykład 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

Wyjście 4

469993557

Przykład 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

Wyjście 5

299529765

Uwagi

W pierwszym teście wynik jest równy oczekiwanej liczbie dni, zanim pojawi się jedyna krawędź w grafie, co wynosi $\frac{1}{0.1} = 10$.

W drugim teście wynik jest równy $\frac{20}{9}$ przed wykonaniem operacji modulo $998\,244\,353$.

W trzecim teście jedyny wierzchołek posiada już wiadomość, więc wynik wynosi 0.