Message Spread

$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}$임을 의미한다.

그래프에는 자기 루프나 다중 간선이 없으며, 모든 간선이 나타난다고 가정할 때 그래프는 연결되어 있음이 보장된다.

입력에 대한 추가 제약 조건: $i$와 $j$ 사이의 간선이 나타날 확률을 $g_{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$이다.

두 번째 테스트에서, 답은 $998\,244\,353$으로 나누기 전 $\frac{20}{9}$와 같다.

세 번째 테스트에서, 유일한 정점은 이미 메시지를 가지고 있으므로 답은 0이다.

네 번째 테스트에서, 답은 $469993557$이다.

다섯 번째 테스트에서, 답은 $299529765$이다.