题目描述

高橋君は家の周りをあてもなく歩き回ることにしました。
散歩の間、高橋君は地点 $1$, 地点 $2$, $\dots$, 地点 $N$ の $N$ か所の地点を歩き回ります。ここで、地点 $1$ は自宅です。
地点間に道が存在するような地点の組は $M$ 組あります。 $i$ 番目の組を $(a_i,\ b_i)$ とした時、地点 $a_i$ と地点 $b_i$ を双方向に結ぶ長さ $d$ $(1\ \leq\ d\ \leq\ T)$ キロメートルの道は $p_{i,\ d}$ 本あります。

高橋君は自宅を出発して $T$ キロメートル歩いて自宅に戻る散歩コースの本数が知りたくなりました。ここで、長さ $T$ キロメートルの散歩コースは次のように定義されます。

• 地点と道を交互に並べた列 $ v_0\ =\ 1,\ e_0,\ v_1,\ \dots,e_{k-1},\ v_k\ =\ 1 $ であって、$e_i$ $(0\ \leq\ i\ \leq\ k-1)$ が $v_i$ と $v_{i+1}$ を結んでいて、 $e_i$ の長さの和が $T$ キロメートルである。

あなたは高橋君のかわりに条件を満たす散歩コースの本数を $998244353$ で割ったあまりを求めてください。ただし、$2$ つの散歩コースは列として異なるときに異なるとみなされます。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $T$ $a_1$ $b_1$ $p_{1,1}$ $p_{1,2}$ $\ldots$ $p_{1,T}$ $\vdots$ $a_M$ $b_M$ $p_{M,1}$ $p_{M,2}$ $\ldots$ $p_{M,T}$

输出格式

条件を満たす散歩コースの本数を $998244353$ で割ったあまりを出力せよ。

题目大意

给定一个 $n$ 个点 $m$ 条边的简单无向图, 每条边边权为一个常数项为 $0$ 的 $T$ 次多项式, 定义路径权值为边权之积, 求所有从 $1$ 号点出发最后回到 $1$ 号点的回路的权值的 $T$ 次项系数和.

3 2 2
1 2
1 0
1 3
2 0

5

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

130

2 1 5
1 2
31415 92653 58979 32384 62643

844557977

提示

制約

• $2\ \leq\ N\ \leq\ 10$
• $ 1\ \leq\ M\ \leq\ \min\ \left(10,\ \frac{N(N-1)}{2}\ \right) $
• $1\ \leq\ T\ \leq\ 4\ \times\ 10^4$
• $1\ \leq\ a_i\ \lt\ b_i\ \leq\ N$
• $i\ \neq\ j$ ならば $(a_i,\ b_i)\ \neq\ (a_j,\ b_j)$
• $0\ \leq\ p_{i,j}\ \lt\ 998244353$

Sample Explanation 1

高橋君の家の周りには、 - 地点 $1$ と地点 $2$ を結ぶ長さ $1$ キロメートルの道が $1$ 本 - 地点 $1$ と地点 $3$ を結ぶ長さ $1$ キロメートルの道が $2$ 本 あります。条件を満たすコースは - 地点 $1$ $\to$ 地点 $2$ $\to$ 地点 $1$ の順に巡るコースが $1\ \times\ 1\ =\ 1$ 通り - 地点 $1$ $\to$ 地点 $3$ $\to$ 地点 $1$ の順に巡るコースが $2\ \times\ 2\ =\ 4$ 通り の計 $5$ 通りです。

Sample Explanation 2

高橋君の家の周りには、 - 地点 $1$ と地点 $2$ を結ぶ長さ $1$ キロメートルの道が $3$ 本 - 地点 $1$ と地点 $3$ を結ぶ長さ $2$ キロメートルの道が $1$ 本 - 地点 $2$ と地点 $3$ を結ぶ長さ $1$ キロメートルの道が $2$ 本 あります。条件を満たすコースは、経由する地点を列挙すると - 地点 $1$ $\to$ 地点 $2$ $\to$ 地点 $1$ $\to$ 地点 $2$ $\to$ 地点 $1$ - 地点 $1$ $\to$ 地点 $2$ $\to$ 地点 $3$ $\to$ 地点 $1$ - 地点 $1$ $\to$ 地点 $2$ $\to$ 地点 $3$ $\to$ 地点 $2$ $\to$ 地点 $1$ - 地点 $1$ $\to$ 地点 $3$ $\to$ 地点 $1$ - 地点 $1$ $\to$ 地点 $3$ $\to$ 地点 $2$ $\to$ 地点 $1$ の $5$ パターンがあり、本数は上から順に $81$ 通り、 $6$ 通り、 $36$ 通り、 $1$ 通り、 $6$ 通りとなります。