{"problem":{"name":"Stroll","description":{"content":"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$ pair","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc213_h"},"statements":[{"statement_type":"Markdown","content":"Takahashi has decided to wander around his house.  \nDuring his walk, he will roam between $N$ points called Point $1$, Point $2$, $\\dots$, Point $N$, where Point $1$ is his house.  \nThere 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$.\nTakahashi 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.\n\n*   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.\n\nHelp Takahashi by finding the number of such courses modulo $998244353$. Two courses are considered different when they are different as sequences.\n\n## Constraints\n\n*   $2 \\leq N \\leq 10$\n*   $1 \\leq M \\leq \\min \\left(10, \\frac{N(N-1)}{2} \\right)$\n*   $1 \\leq T \\leq 4 \\times 10^4$\n*   $1 \\leq a_i \\lt b_i \\leq N$\n*   $(a_i, b_i) \\neq (a_j, b_j)$ if $i \\neq j$.\n*   $0 \\leq p_{i,j} \\lt 998244353$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$ $T$\n$a_1$ $b_1$\n$p_{1,1}$ $p_{1,2}$ $\\ldots$ $p_{1,T}$\n$\\vdots$\n$a_M$ $b_M$\n$p_{M,1}$ $p_{M,2}$ $\\ldots$ $p_{M,T}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc213_h","tags":[],"sample_group":[["3 2 2\n1 2\n1 0\n1 3\n2 0","5\n\nAround his house, there are:\n\n*   one $1$\\-kilometer road connecting Point $1$ and Point $2$, and\n*   two $1$\\-kilometer roads connecting Point $1$ and Point $3$.\n\nWe have the following five desirable courses:\n\n*   $1 \\times 1 = 1$ course that goes Point $1$ $\\to$ Point $2$ $\\to$ Point $1$, and\n*   $2 \\times 2 = 4$ courses that goes Point $1$ $\\to$ Point $3$ $\\to$ Point $1$."],["3 3 4\n1 2\n3 0 0 0\n1 3\n0 1 0 0\n2 3\n2 0 0 0","130\n\nAround his house, there are:\n\n*   three $1$\\-kilometer roads connecting Point $1$ and Point $2$,\n*   one $2$\\-kilometer road connecting Point $1$ and Point $3$, and\n*   two $1$\\-kilometer roads connecting Point $2$ and Point $3$.\n\nThe desirable courses can be classified into the following categories, according to the points visited:\n\n*   Point $1$ $\\to$ Point $2$ $\\to$ Point $1$ $\\to$ Point $2$ $\\to$ Point $1$,\n*   Point $1$ $\\to$ Point $2$ $\\to$ Point $3$ $\\to$ Point $1$,\n*   Point $1$ $\\to$ Point $2$ $\\to$ Point $3$ $\\to$ Point $2$ $\\to$ Point $1$,\n*   Point $1$ $\\to$ Point $3$ $\\to$ Point $1$, and\n*   Point $1$ $\\to$ Point $3$ $\\to$ Point $2$ $\\to$ Point $1$.\n\nWe have $81$, $6$, $36$, $1$, and $6$ course(s) of these categories, respectively."],["2 1 5\n1 2\n31415 92653 58979 32384 62643","844557977"]],"created_at":"2026-03-03 11:01:13"}}