給定一個包含 $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$ 之間邊出現的機率（若 $i$ 與 $j$ 之間沒有邊，則 $g_{i,j} = 0$）。保證對於任何 $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}$ 的整數。換句話說，輸出一個滿足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod{M}$ 的整數 $x$。

範例

輸入格式 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