Problem Description

Before band f goes on tour, by tradition they first organize a dice trip for the band members to relax. A dice trip includes $N$ locations, numbered $1, 2, \cdots, N$. The band members agree in advance to meet at $s_0$; on the day of the dice trip, everyone arrives at the meeting point $s_0$, and the dice trip officially begins.

A major fun part of a dice trip is that a die decides the next destination. Of course, the die does not have to be six-sided. We can assume that if the band members are currently at location $i$, then the next destination is chosen uniformly at random from $m_i$ distinct candidate locations, namely $l_{i, 1}, l_{i, 2}, \cdots, l_{i, m_i}$. Let the result of the $t$-th roll be $s_t$. Then before the $(t+1)$-th roll, they will go to $s_t$ to roll the die. The first roll is performed at the starting point $s_0$. Since the band still needs to rehearse for the tour afterward, they agree in advance that no matter which locations they go to, after rolling the die for the $T$-th time and then going to $s_T$, the dice trip must end.

Of course, enjoying the scenery of $s_0, s_1, \cdots, s_T$ is also a big part of the trip. Whether they have been there before or not, every time they arrive at a location $s_t$, the band members will fully enjoy the views and taste the local food. However, if they have been to $s_t$ before, then before rolling the $(t+1)$-th die, the keyboardist S, who is responsible for rolling, will definitely say: “The last time we came to $s_t$ seems like it was at time $t'$. Last time we rolled $s_{t'+1}$ here. I wonder what we will roll this time.” The drummer Y especially likes this kind of chatter, so every time S says this sentence, he writes down $s_{t'+1}$. In particular, if $s_T$ is a location visited before, then S will say: “The last time we came to $s_t$ seems like it was at time $t'$. Last time we rolled $s_{t'+1}$ here, but this time we will not roll, because the dice trip is about to end here.” Of course, Y will also write down this $s_{t'+1}$.

As a summary of this dice trip, Y will add up all the recorded $s_{t'+1}$, and use it as S’s “chatter index”.

Band f’s next tour is about to start, so S is planning to take everyone on a dice trip again. Hearing that you are a fan of f, S comes to you and hopes you can help him compute the expected value of the chatter index for this dice trip.

Input Format

The first line contains three positive integers $N, s_0, T$, representing the number of locations that may be involved, the starting location of the dice trip, and the number of die rolls during the dice trip.

The next $N$ lines describe the transitions. In the $i$-th line $(1\le i\le N)$, first input a positive integer $m_i$, representing the number of candidate next destinations from location $i$; then input $m_i$ positive integers, representing these $m_i$ locations $l_{i, 1}, l_{i, 2}, \cdots, l_{i, m_i}$. It is guaranteed that for any $i$, the $m_i$ input locations are pairwise distinct.

Output Format

Output one number representing the expected value of the chatter index. Suppose the expected value of the chatter index is reduced to the simplest fraction $p/q$ (i.e. $p$ and $q$ are coprime). Output $x$ such that $qx\equiv p \pmod{998,244,353}$ and $0\le x<998,244,353$. It can be proven that under the Constraints of this problem, such an $x$ exists and is unique.

5 1 2
3 2 3 4
2 1 5
2 1 5
2 1 5
3 2 3 4

499122178

7 1 4
6 2 3 4 5 6 7
6 1 3 4 5 6 7
6 1 2 4 5 6 7
6 1 2 3 5 6 7
6 1 2 3 4 6 7
6 1 2 3 4 5 7
6 1 2 3 4 5 6

274979351

Hint

【Sample Explanation 1】

The paths that contribute to the answer are: start from node $1$, go to any node among $2, 3, 4$, and return to node $1$. For a certain node $i (i=2, 3, 4)$, the probability of going to node $i$ and then returning to node $1$ is $1/6$, and the contribution is $i$, so the expectation is

Since $499122178 \times 2 = 998244356 \equiv 3 \pmod {998244353}$, we know that $3/2$ modulo $998,244,353$ is $499,122,178$, so the correct output is $499,122,178$.

【Sample Explanation 2】

The answer before taking modulo is $1625/432\approx 3.761574$, and $432\times 274979351 = 118791079632 \equiv 1625 \pmod{998244353}$, so the answer modulo is $274979351$.

【Sample 3】

See the attachment.

【Constraints】

For $100\%$ of the testdata, it is guaranteed that $1\le N\le 100$, $1\le T\le 100$, $1\le s_0\le N$, $1\le m_i\le N$, $\sum_{i=1}^N m_i\le 5000$, $1\le l_{i, j}\le N$, and $\forall 1\le i\le N, \forall 1\le j_1<j_2\le m_i, l_{i, j_1}\ne l_{i, j_2}$。

Translated by ChatGPT 5