← 返回题目列表

AtCoder · abc213_h

H. 漫步

中文机器翻译题面 查看原题

分数: 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