$n$ 個の頂点と $m$ 本の辺を持つ無向グラフが与えられる。各辺は2つの頂点 $(u, v)$ を結び、毎日 $\frac{p}{q}$ の確率で出現する。

最初、頂点 1 がメッセージを持っている。ある日の終わりに、その頂点自身がメッセージを持っていたか、あるいは隣接する頂点の少なくとも1つが前日にメッセージを持っていた場合、その頂点はメッセージを持つ。各日、各辺は独立して出現するかどうかを選択することに注意せよ。

すべての頂点がメッセージを持つようになるまでの日数の期待値を、998 244 353 を法として計算せよ。

入力

1行目に2つの整数 $n$ と $m$ ($1 \le n \le 21, n - 1 \le m \le \frac{n(n-1)}{2}$) が与えられる。

続く $m$ 行には、それぞれ4つの整数 $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) \neq 1 \pmod{998 244 353}$$

出力

すべての頂点がメッセージを持つようになるまでの日数の期待値を、998 244 353 を法として1行に出力せよ。

形式的には、$M = 998 244 353$ とする。答えは既約分数 $\frac{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

入力 2

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

出力 2

887328316

入力 3

1 0

出力 3

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

注記

1つ目のテストケースでは、答えはグラフ内の唯一の辺が最初に出現するまでの日数の期待値に等しく、それは $\frac{1}{0.1} = 10$ である。

2つ目のテストケースでは、答えは 998 244 353 を法とする前の値が $\frac{20}{9}$ に等しい。

3つ目のテストケースでは、唯一の頂点がすでにメッセージを持っているため、答えは 0 である。