H - 闲逛

得分: $600$ 分

问题描述

高桥决定在他的房子周围闲逛。在他的行走过程中，他会在点 $1$，点 $2$，$\dots$，点 $N$ 之间漫游，其中点 $1$ 是他的房子。
这 $N$ 个点之间有 $M$ 对通过道路连接的点；设 $(a_i, b_i)$ 是第 $i$ 对这样的点。有 $p_{i, d}$ 条长度为 $d$ $(1 \leq d \leq T)$ 千米的道路连接着点 $a_i$ 和点 $b_i$。

高桥想知道从他的房子开始并结束的总长度为 $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 \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$ 取模。

3 2 2
1 2
1 0
1 3
2 0

5

在他的房子周围，有：

• 一条连接点 $1$ 和点 $2$ 的 $1$ 千米路，和
• 两条连接点 $1$ 和点 $3$ 的 $1$ 千米路。

这里有以下五条合适的线路：

• 走过 Point $1$ $\to$ Point $2$ $\to$ Point $1$ 的 $1$ 条线路；
• 走过 Point $1$ $\to$ Point $3$ $\to$ Point $1$ 的 $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$ 千米路，
• 一条连接点 $1$ 和点 $3$ 的 $2$ 千米路，和
• 两条连接点 $2$ 和点 $3$ 的 $1$ 千米路。

对于合适的线路，根据访问的点进行分类，可得到以下结果：

• Point $1$ $\to$ Point $2$ $\to$ Point $1$ $\to$ Point $2$ $\to$ Point $1$ 的线路有 $81$ 条；
• Point $1$ $\to$ Point $2$ $\to$ Point $3$ $\to$ Point $1$ 的线路有 $6$ 条；
• Point $1$ $\to$ Point $2$ $\to$ Point $3$ $\to$ Point $2$ $\to$ Point $1$ 的线路有 $36$ 条；
• Point $1$ $\to$ Point $3$ $\to$ Point $1$ 的线路有 $1$ 条；
• Point $1$ $\to$ Point $3$ $\to$ Point $2$ $\to$ Point $1$ 的线路有 $6$ 条。

因此符合条件的线路共有 $130$ 条。

2 1 5
1 2
31415 92653 58979 32384 62643

844557977