暂无测试数据。

「天空度假山庄」中有一个 $n$ 点 $m$ 边的无向图，图中点的编号分别为 $1,2,\cdots,n$，边的编号分别为 $1,2,\cdots,m$。

度假山庄已经很久没有打扫了，因此图中的边已经模糊不清。

具体来说：

• 第 $i$ 条边连接的两个端点分别为 $u_i$ 和 $v_i$。
• 这条边上落下了许多灰尘，因此云浅有 $p_i$ 的概率看不到这条边。这里保证 $0\le p_i\le 1,p_i\in \mathbb Q$。

在云浅看到的图中，若 $1$ 号点所在的连通块大小为 $x$，则云浅会认为这张图的「美观程度」为 $x^2$。

云浅想要求出这张图的「美观程度」的期望值。她还要帮 $\text{Oshiro}$ 打扫山庄，因此她找到了你求助。

为了避免精度误差，本题的输入输出格式较为特殊，详细信息将在【输入格式】与【输出格式】中说明。

输入格式

第一行两个正整数 $n,m$。

接下来 $m$ 行，第 $i+1$ 行有 $4$ 个正整数 $u_i,v_i,x_i,y_i$，表示一条边。其中：

• $u_i,v_i$ 表示这条边的两个端点。
• 云浅看不到这条边的概率即为 $p_i=\frac{x_i}{x_i+y_i}$。

输出格式

一行一个正整数表示这张图的「美观程度」的期望值。

为了避免精度误差，你只需要求出答案对 $998244353$ 取模后的值即可。

更具体地，设答案为 $\frac{A}{B}$，其中 $\gcd(A,B)=1$，你需要输出一个 $C$ 使得 $B\times C\equiv A \;(\bmod\; 998244353)$。

可以证明这样的 $C$ 一定存在且唯一。

数据范围

对于 $100\%$ 的数据，$1\le n\le 17,1\le m\le \dfrac{n(n-1)}{2},1\le x_i,y_i < 998244353, x_i + y_i \neq 998244353$。

4 4
1 2 1 1
2 3 1 2
3 1 1 3
2 4 2 3

465847375

2 2
1 2 1 8
2 1 2 4

554580200