Score : $600$ points
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.
Help Takahashi by finding the number of such courses modulo $998244353$. Two courses are considered different when they are different as sequences.
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}$
Print the number of desirable courses, modulo $998244353$.
3 2 2 1 2 1 0 1 3 2 0
5
Around his house, there are:
We have the following five desirable courses:
3 3 4 1 2 3 0 0 0 1 3 0 1 0 0 2 3 2 0 0 0
130
Around his house, there are:
The desirable courses can be classified into the following categories, according to the points visited:
We have $81$, $6$, $36$, $1$, and $6$ course(s) of these categories, respectively.
2 1 5 1 2 31415 92653 58979 32384 62643
844557977