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$.