Given an undirected graph with $n$ vertices and $m$ edges. Each edge connects two vertices $(u, v)$ and has a probability of $\frac{p}{q}$ of appearing each day.

Initially, vertex 1 has a message. At the end of the day, a vertex has a message if and only if itself or at least one of the vertices adjacent to it had the message the day before. Note that each day, each edge chooses its appearance independently.

Calculate the expected number of days before all the vertices have the message, modulo $998\,244\,353$.

Input

The first line contains two integers $n$ and $m$ ($1 \le n \le 21$, $n - 1 \le m \le \frac{n(n-1)}{2}$).

Then $m$ lines follow, each containing four integers $u$, $v$, $p$, and $q$ ($1 \le u \neq v \le n$, $1 \le p < q < 998\,244\,353$, $\gcd(p, q) = 1$) — there is an undirected edge between $u$ and $v$, and it has a probability of appearance of $\frac{p}{q}$ each day.

It is guaranteed that there are no self-loops or multiple-edges in the graph and that the graph is connected if all of the edges appear.

Additional constraint in the input: Let $g_{i,j}$ be the probability of appearance of the edge between $i$ and $j$ ($g_{i,j} = 0$ if there is no edge between $i$ and $j$). It is guaranteed that for any $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}.$$

Output

Print a single integer in the only line of the output — the expected number of days, modulo $998\,244\,353$.

Formally, let $M = 998\,244\,353$. It can be shown that the exact answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not\equiv 0 \pmod{M}$. Output the integer equal to $p \cdot q^{-1} \pmod{M}$. In other words, output such an integer $x$ that $0 \le x < M$ and $x \cdot q \equiv p \pmod{M}$.

Examples

Input 1

2 1
1 2 1 10

Output 1

10

Note

In the first test, the answer is equal to the expected number of days before the only edge in the graph first appears, and that is $\frac{1}{0.1} = 10$.

Input 2

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

Output 2

887328316

Note

In the second test, the answer is equal to $\frac{20}{9}$ before it is taken modulo $998\,244\,353$.

Input 3

1 0

Output 3

0

Note

In the third test, the only vertex already has the message, so the answer is 0.

Input 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

Output 4

469993557

Input 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

Output 5

299529765