On considère un graphe non orienté avec $n$ sommets et $m$ arêtes. Chaque arête relie deux sommets $(u, v)$ et a une probabilité de $\frac{p}{q}$ d'apparaître chaque jour.

Initialement, le sommet 1 possède un message. À la fin de la journée, un sommet possède le message si et seulement si lui-même ou au moins l'un des sommets qui lui sont adjacents possédait le message la veille. Notez que chaque jour, chaque arête choisit son apparition indépendamment.

Calculez le nombre attendu de jours avant que tous les sommets possèdent le message, modulo 998 244 353.

Entrée

La première ligne contient deux entiers $n$ et $m$ ($1 \le n \le 21$, $n - 1 \le m \le \frac{n(n-1)}{2}$).

Ensuite, $m$ lignes suivent, chacune contenant quatre entiers $u$, $v$, $p$ et $q$ ($1 \le u \neq v \le n$, $1 \le p < q < 998 244 353$, $\gcd(p, q) = 1$) — il existe une arête non orientée entre $u$ et $v$, et elle a une probabilité d'apparition de $\frac{p}{q}$ chaque jour.

Il est garanti qu'il n'y a pas de boucles ou d'arêtes multiples dans le graphe et que le graphe est connexe si toutes les arêtes apparaissent.

Contrainte supplémentaire sur l'entrée : Soit $g_{i,j}$ la probabilité d'apparition de l'arête entre $i$ et $j$ ($g_{i,j} = 0$ s'il n'y a pas d'arête entre $i$ et $j$). Il est garanti que pour tout $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}.$$

Sortie

Affichez un seul entier sur la seule ligne de sortie — le nombre attendu de jours, modulo 998 244 353.

Formellement, soit $M = 998 244 353$. On peut montrer que la réponse exacte peut être exprimée sous la forme d'une fraction irréductible $\frac{p}{q}$, où $p$ et $q$ sont des entiers et $q \not\equiv 0 \pmod M$. Affichez l'entier égal à $p \cdot q^{-1} \pmod M$. En d'autres termes, affichez un entier $x$ tel que $0 \le x < M$ et $x \cdot q \equiv p \pmod M$.

Exemples

Entrée 1

2 1
1 2 1 10

Sortie 1

10

Entrée 2

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

Sortie 2

887328316

Entrée 3

1 0

Sortie 3

0

Entrée 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

Sortie 4

469993557

Entrée 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

Sortie 5

299529765

Remarque

Dans le premier test, la réponse est égale au nombre attendu de jours avant que la seule arête du graphe n'apparaisse pour la première fois, ce qui est $\frac{1}{0.1} = 10$.

Dans le deuxième test, la réponse est égale à $\frac{20}{9}$ avant d'être prise modulo 998 244 353.

Dans le troisième test, le seul sommet possède déjà le message, donc la réponse est 0.