Problem Description

给出一张$n$个点$m$条边的无向图，第$i$条边连接$u,v$,在第$j$天出现的概率为$p_i+\frac{j}{k_i}$

求这一张图从第一天到第$T$天每天期望生成树的个数的和,答案对$998244353$取模

注意图上可能会有重边出现，由于一些神奇的原因，若有重边出现两点之间有边的概率为所有重边概率相加的和

Input

第一行三个正整数 $n,m,T$

接下来$m$行,每行$5$个整数$u_i,v_i,a_i,b_i,k_i$

其中$p_i=\frac{a_i}{b_i}$,保证每个概率的实际值$\le 1$,给出的$a_i,b_i$仅代表模意义下

保证对于一条存在的边，其重边的$\sum \frac{1}{k_i} \neq 0$ $mod$ $998244353$

$2\leq n\leq 400,1\leq m \le 100000,1 \le u_i,v_i\le n,1\le a_i,b_i,k_i\le 10^8,1\le T \le 10^9$

Output

输出一个整数，表示要求的答案

样例输入1:
2 1 5
1 2 1 1 1
样例输入2:
3 3 10
1 2 1 3 1
2 3 2 1 3
3 1 3 3 4

样例输出1:
20
样例输出2:
27729518