题目描述
在乐队 f 开巡演之前,按照惯例是要先组织乐队成员进行骰子旅行放松身心的。一次骰子旅行包括 $N$ 个地点,这些地点分别标号为 $1, 2, \cdots, N$。乐队成员们事先约好在 $s_0$ 处集合;而到了骰子旅行当天,大家都来到了集合地点 $s_0$,骰子旅行就算正式开始了。
骰子旅行的一大乐趣就是由骰子决定旅行的下一个目的地。当然,这个骰子不一定非得是六面的。我们可以认为,如果当前乐队成员们位于地点 $i$,那么下一个目的地会等概率地从 $m_i$ 个互不相同的候选地点中产生,这些候选地点分别是 $l_{i, 1}, l_{i, 2}, \cdots, l_{i, m_i}$。我们记第 $t$ 次投掷的结果是 $s_t$,那么第 $(t+1)$ 次将会前往 $s_t$ 处掷骰子。第 1 次投掷在起点 $s_0$ 处进行;而由于乐队之后还需要为了巡演排练,事先约定无论前往了哪些地点,投掷完第 $T$ 次骰子,前往 $s_T$ 后骰子旅行都得结束。
当然,享受 $s_0, s_1, \cdots, s_T$ 这些景点也是骰子旅行的一大乐趣。无论是否之前来过,每次到一个地点 $s_t$,乐队成员们都会尽情地浏览美景,品尝美食。只是如果之前来过 $s_t$,负责掷骰子的键盘手 S 在掷这第 $(t+1)$ 次骰子之前一定会说:“上次来到 $s_t$ 仿佛还是上一次 $t'$,上一次在这里掷出了 $s_{t'+1}$,不知道这一次会掷出什么结果。”鼓手 Y 特别喜欢废话梗,所以每次 S 说这句话时,他都会把 $s_{t'+1}$ 记下来。特别地,如果 $s_T$ 是之前经过的地点,那么 S 会说:“上次来到 $s_t$ 仿佛还是上一次 $t'$,上一次在这里掷出了 $s_{t'+1}$,不过这一次就不投掷了,因为骰子旅行到这里就要告一段落了。”当然,Y 也会把这个 $s_{t'+1}$ 记下来。
作为这次骰子旅行的总结,Y 会把所有记录下来的 $s_{t'+1}$ 加起来,作为 S 的废话指数。
f 的下一次巡演马上就要开始了,于是 S 又盘算着带大家去参加骰子旅行。听说你是 f 的粉丝,S 找到了你,希望你能帮他算一下他这次骰子旅行的废话指数的期望值。
输入格式
从标准输入读入数据。
输入的第一行包括三个正整数 $N, s_0, T$,分别表示可能涉及地点的个数,骰子旅行的起点和骰子旅行中投掷骰子的次数。
接下来 $N$ 行,第 $i\ (1\le i\le N)$ 行先输入一个正整数 $m_i$,表示地点 $i$ 的下一个目的地的候选地点数;接着输入 $m_i$ 个正整数,表示这 $m_i$ 个地点 $l_{i, 1}, l_{i, 2}, \cdots, l_{i, m_i}$。保证对于任意 $i$,$m_i$ 个输入的地点互不相同。
输出格式
输出到标准输出。
输出一个数表示废话指数的期望。假设废话指数的期望化为最简分式后的形式为 $p/q$(即其中 $p, q$ 互质),请输出 $x$ 使得 $qx\equiv p \pmod{998,244,353}$ 且 $0\le x< 998,244,353$。可以证明,在本题数据范围下,$x$ 存在且唯一。
样例1输入
5 1 2
3 2 3 4
2 1 5
2 1 5
2 1 5
3 2 3 4
样例1输出
499122178
样例1解释
对答案有贡献的方案为:从点 $1$ 出发走到 $2, 3, 4$ 中的任意一个点并返回点 $1$。对于某个点 $i (i=2, 3, 4)$,走到点 $i$ 并返回点 $1$ 的概率为 $1/6$,而贡献为 $i$,故期望为 $$\frac{1}{6}\times (2+3+4) = \frac{3}{2}.$$
由 $499122178 \times 2 = 998244356 \equiv 3 \pmod {998244353}$ 可知 $3/2$ 在模 $998,244,353$ 意义下为 $499,122,178$,所以正确输出为 $499,122,178$。
样例2输入
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
样例2输出
274979351
样例2解释
转换前的答案为 $1625/432\approx 3.761574$,而 $432\times 274979351 = 118791079632 \equiv 1625 \pmod{998244353}$,所以模意义下的答案为 $274979351$。
样例3
见题目目录下的 3.in 与 3.ans。
子任务
对于 $100\%$ 的数据,保证 $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$,且 $\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}$。