/ 
Time Limit: 5 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
高橋君は家の周りをあてもなく歩き回ることにしました。
散歩の間、高橋君は地点 1, 地点 2, \dots, 地点 N の N か所の地点を歩き回ります。ここで、地点 1 は自宅です。
地点間に道が存在するような地点の組は M 組あります。 i 番目の組を (a_i, b_i) とした時、地点 a_i と地点 b_i を双方向に結ぶ長さ d (1 \leq d \leq T) キロメートルの道は p_{i, d} 本あります。
高橋君は自宅を出発して 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 つの散歩コースは列として異なるときに異なるとみなされます。
制約
- 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 本
- 地点 1 と地点 3 を結ぶ長さ 1 キロメートルの道が 2 本
あります。条件を満たすコースは
- 地点 1 \to 地点 2 \to 地点 1 の順に巡るコースが 1 \times 1 = 1 通り
- 地点 1 \to 地点 3 \to 地点 1 の順に巡るコースが 2 \times 2 = 4 通り
の計 5 通りです。
入力例 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 キロメートルの道が 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
の 5 パターンがあり、本数は上から順に 81 通り、 6 通り、 36 通り、 1 通り、 6 通りとなります。
入力例 3
2 1 5 1 2 31415 92653 58979 32384 62643
出力例 3
844557977
Score : 600 points
Problem Statement
Takahashi has decided to wander around his house.
During his walk, he will roam between N points called Point 1, Point 2, \dots, Point N, where Point 1 is his house.
There are M pairs of points connected by roads; let (a_i, b_i) be the i-th of these pairs. There are p_{i, d} roads with a length of d (1 \leq d \leq T) kilometers connecting Point a_i and Point b_i.
Takahashi wants to know the number of T kilometers courses that begin and end at his house. Here, a T kilometers course is defined as follows.
- An alternating sequence with points and roads v_0 = 1, e_0, v_1, \dots,e_{k-1}, v_k = 1 such that e_i (0 \leq i \leq k-1) connects v_i and v_{i+1}, and the total length of e_i is T kilometers.
Help Takahashi by finding the number of such courses modulo 998244353. Two courses are considered different when they are different as sequences.
Constraints
- 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
Input
Input is given from Standard Input in the following format:
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}
Output
Print the number of desirable courses, modulo 998244353.
Sample Input 1
3 2 2 1 2 1 0 1 3 2 0
Sample Output 1
5
Around his house, there are:
- one 1-kilometer road connecting Point 1 and Point 2, and
- two 1-kilometer roads connecting Point 1 and Point 3.
We have the following five desirable courses:
- 1 \times 1 = 1 course that goes Point 1 \to Point 2 \to Point 1, and
- 2 \times 2 = 4 courses that goes Point 1 \to Point 3 \to Point 1.
Sample Input 2
3 3 4 1 2 3 0 0 0 1 3 0 1 0 0 2 3 2 0 0 0
Sample Output 2
130
Around his house, there are:
- three 1-kilometer roads connecting Point 1 and Point 2,
- one 2-kilometer road connecting Point 1 and Point 3, and
- two 1-kilometer roads connecting Point 2 and Point 3.
The desirable courses can be classified into the following categories, according to the points visited:
- Point 1 \to Point 2 \to Point 1 \to Point 2 \to Point 1,
- Point 1 \to Point 2 \to Point 3 \to Point 1,
- Point 1 \to Point 2 \to Point 3 \to Point 2 \to Point 1,
- Point 1 \to Point 3 \to Point 1, and
- Point 1 \to Point 3 \to Point 2 \to Point 1.
We have 81, 6, 36, 1, and 6 course(s) of these categories, respectively.
Sample Input 3
2 1 5 1 2 31415 92653 58979 32384 62643
Sample Output 3
844557977