Se da un grafo no dirigido con $n$ vértices y $m$ aristas. Cada arista conecta dos vértices $(u, v)$ y tiene una probabilidad de $\frac{p}{q}$ de aparecer cada día.

Inicialmente, el vértice 1 tiene un mensaje. Al final del día, un vértice tiene un mensaje si y solo si él mismo o al menos uno de los vértices adyacentes a él tenía el mensaje el día anterior. Tenga en cuenta que cada día, cada arista elige su aparición de forma independiente.

Calcule el número esperado de días antes de que todos los vértices tengan el mensaje, módulo $998\,244\,353$.

Entrada

La primera línea contiene dos enteros $n$ y $m$ ($1 \le n \le 21$, $n - 1 \le m \le \frac{n(n-1)}{2}$).

Luego siguen $m$ líneas, cada una conteniendo cuatro enteros $u, v, p$ y $q$ ($1 \le u \neq v \le n$, $1 \le p < q < 998\,244\,353$, $\gcd(p, q) = 1$) — hay una arista no dirigida entre $u$ y $v$, y tiene una probabilidad de aparición de $\frac{p}{q}$ cada día.

Se garantiza que no hay bucles ni aristas múltiples en el grafo y que el grafo es conexo si todas las aristas aparecen.

Restricción adicional en la entrada: Sea $g_{i,j}$ la probabilidad de aparición de la arista entre $i$ y $j$ ($g_{i,j} = 0$ si no hay arista entre $i$ y $j$). Se garantiza que para cualquier $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}.$$

Salida

Imprima un solo entero en la única línea de la salida — el número esperado de días, módulo $998\,244\,353$.

Formalmente, sea $M = 998\,244\,353$. Se puede demostrar que la respuesta exacta se puede expresar como una fracción irreducible $\frac{p}{q}$, donde $p$ y $q$ son enteros y $q \not\equiv 0 \pmod{M}$. Imprima el entero igual a $p \cdot q^{-1} \pmod{M}$.

En otras palabras, imprima un entero $x$ tal que $0 \le x < M$ y $x \cdot q \equiv p \pmod{M}$.

Ejemplos

Entrada 1

2 1
1 2 1 10

Salida 1

10

Entrada 2

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

Salida 2

887328316

Entrada 3

1 0

Salida 3

0

Entrada 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

Salida 4

469993557

Entrada 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

Salida 5

299529765

Nota

En la primera prueba, la respuesta es igual al número esperado de días antes de que aparezca la única arista en el grafo, y eso es $\frac{1}{0.1} = 10$.

En la segunda prueba, la respuesta es igual a $\frac{20}{9}$ antes de tomarla módulo $998\,244\,353$.

En la tercera prueba, el único vértice ya tiene el mensaje, por lo que la respuesta es 0.