问题陈述

Takahashi决定在他的房子周围闲逛。在散步时，他将在称为Point 1、Point 2、$\\dots$、Point N的N个点之间漫游，其中Point 1是他的房子。有M对由道路连接的点；设$(a_i, b_i)$为第i对的点。有$p_{i, d}$条长度为d（$1 \\leq d \\leq T$）公里的道路连接点$a_i$和点$b_i$。

Takahashi想知道以他的房子为起点和终点的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$下这些路径的数量来帮助Takahashi。当作为序列时两条路径不同。

约束条件

• $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$

输入

输入以以下格式从标准输入给出：

$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$。

示例输入1

3 2 2
1 2
1 0
1 3
2 0

示例输出1

5

在他的房子周围有：

• 一条连接点1和点2的1公里道路，
• 两条连接点1和点3的1公里道路。

我们有以下五个称心如意的路径：

• $1 \\times 1 = 1$ 条路径从点1 $\\to$ 点2 $\\to$ 点1，
• $2 \\times 2 = 4$ 条路径从点1 $\\to$ 点3 $\\to$ 点1。

示例输入2

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

示例输出2

130

在他的房子周围有：

• 三条连接点1和点2的1公里道路，
• 一条连接点1和点3的2公里道路，
• 两条连接点2和点3的1公里道路。

根据访问的点，令人满意的路径可以分为以下几类：

• 点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。

我们分别有81、6、36、1和6条路径。

示例输入3

2 1 5
1 2
31415 92653 58979 32384 62643

示例输出3

844557977