给定一个包含 $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

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

说明

在第一个测试中，答案等于图中唯一一条边首次出现前的期望天数，即 $\frac{1}{0.1} = 10$。

在第二个测试中，答案等于 $\frac{20}{9}$ 对 $998\,244\,353$ 取模的结果。

在第三个测试中，唯一的顶点已经拥有消息，因此答案为 0。

在第四个测试中，答案为 $469993557$。

在第五个测试中，答案为 $299529765$。