散步

题目描述

高桥君决定在自家附近散步。

散步过程中,他会在 $N$ 个点之间往返,这些点称为点 $1$、点 $2$、$\dots$、点 $N$,其中点 $1$ 是他的家。

有 $M$ 对由道路连接的点;设 $(a_i, b_i)$ 为其中的第 $i$ 对。连接点 $a_i$ 和点 $b_i$ 的长度为 $d$($1 \le d \le T$)千米的道路有 $p_{i, d}$ 条。

高桥君想知道从家出发又回到家的总长度为 $T$ 千米的路线有多少条。这里,长度为 $T$ 千米的路线定义如下。

一个由点和道路交替组成的序列 $v_0 = 1, e_0, v_1, \dots,e_{k-1}, v_k = 1$,满足 $e_i$($0 \le i \le k-1$)连接 $v_i$ 和 $v_{i+1}$,且 $e_i$ 的长度之和为 $T$ 千米。

请帮助高桥君求出这样的路线数量对 $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$ 取模后的值。

样例

3 2 2
1 2
1 0
1 3
2 0

5

他家附近有:

连接点 $1$ 和点 $2$ 的 $1$ 千米道路 $1$ 条,

连接点 $1$ 和点 $3$ 的 $1$ 千米道路 $2$ 条。

有以下 5 条符合条件的路线:

经过点 $1 \to$ 点 $2 \to$ 点 $1$ 的路线有 $1 \times 1 = 1$ 条,

经过点 $1 \to$ 点 $3 \to$ 点 $1$ 的路线有 $2 \times 2 = 4$ 条。

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

130

他家附近有:

连接点 $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$。

这些类别的路线分别有 $81$、$6$、$36$、$1$、$6$ 条。

2 1 5
1 2
31415 92653 58979 32384 62643

844557977

数据范围

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