Cho một đồ thị vô hướng gồm $n$ đỉnh và $m$ cạnh. Mỗi cạnh nối hai đỉnh $(u, v)$ và có xác suất xuất hiện là $\frac{p}{q}$ vào mỗi ngày.

Ban đầu, đỉnh 1 có một thông điệp. Vào cuối mỗi ngày, một đỉnh sẽ có thông điệp nếu và chỉ nếu chính nó hoặc ít nhất một trong các đỉnh kề với nó đã có thông điệp từ ngày hôm trước. Lưu ý rằng mỗi ngày, mỗi cạnh đều chọn trạng thái xuất hiện của nó một cách độc lập.

Hãy tính kỳ vọng số ngày để tất cả các đỉnh đều có thông điệp, theo modulo $998\,244\,353$.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$ và $m$ ($1 \le n \le 21$, $n - 1 \le m \le \frac{n(n-1)}{2}$).

Tiếp theo là $m$ dòng, mỗi dòng chứa bốn số nguyên $u, v, p$ và $q$ ($1 \le u \neq v \le n$, $1 \le p < q < 998\,244\,353$, $\gcd(p, q) = 1$) — có một cạnh vô hướng giữa $u$ và $v$, và cạnh này có xác suất xuất hiện là $\frac{p}{q}$ mỗi ngày.

Đảm bảo rằng không có khuyên hay đa cạnh trong đồ thị và đồ thị liên thông nếu tất cả các cạnh đều xuất hiện.

Ràng buộc bổ sung trong dữ liệu vào: Gọi $g_{i,j}$ là xác suất xuất hiện của cạnh giữa $i$ và $j$ ($g_{i,j} = 0$ nếu không có cạnh giữa $i$ và $j$). Đảm bảo rằng với mọi $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) \equiv 1 \pmod{998\,244\,353}$$

Dữ liệu ra

In ra một số nguyên duy nhất trên một dòng — kỳ vọng số ngày, theo modulo $998\,244\,353$.

Về mặt hình thức, gọi $M = 998\,244\,353$. Có thể chứng minh rằng đáp án chính xác có thể biểu diễn dưới dạng phân số tối giản $\frac{p}{q}$, trong đó $p$ và $q$ là các số nguyên và $q \not\equiv 0 \pmod{M}$. Hãy in ra số nguyên bằng $p \cdot q^{-1} \pmod{M}$. Nói cách khác, in ra số nguyên $x$ sao cho $0 \le x < M$ và $x \cdot q \equiv p \pmod{M}$.

Ví dụ

Dữ liệu vào 1

2 1
1 2 1 10

Dữ liệu ra 1

10

Dữ liệu vào 2

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

Dữ liệu ra 2

887328316

Dữ liệu vào 3

1 0

Dữ liệu ra 3

0

Dữ liệu vào 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

Dữ liệu ra 4

469993557

Dữ liệu vào 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

Dữ liệu ra 5

299529765

Ghi chú

Trong ví dụ đầu tiên, đáp án bằng kỳ vọng số ngày trước khi cạnh duy nhất trong đồ thị xuất hiện lần đầu tiên, đó là $\frac{1}{0.1} = 10$.

Trong ví dụ thứ hai, đáp án bằng $\frac{20}{9}$ trước khi lấy modulo $998\,244\,353$.

Trong ví dụ thứ ba, đỉnh duy nhất đã có thông điệp, vì vậy đáp án là 0.