分数: 600 点
问题陈述
高桥决定在他的房子里闲逛。
在行走过程中,他会在 N 点称为Point 1, 点 2, \dots, 点 N,其中点 1 是他的房子。
有 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 is 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
- (a_i, b_i) \neq (a_j, b_j) if i \neq 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-公里道路连接点 1 和点 2,和
- 两个 1-公里道路连接点 1 和点 3.
我们有以下五门理想的课程:
- 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-公里道路连接点 1 和点 2,
- 一 2-公里道路连接点 1 和点 3,和
- 两个 1-公里道路连接点 2 和点 3.
根据访问点,理想的课程可以分为以下几类: 分别是这些类别的
- 点 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