题目描述

有一个长度为 $n$ 的排列 $p$ （$1\sim n$ 恰好在 $p$ 中各出现一次）和一个变量 $x$，初始时 $x$ 为 $k$。

接下来你需要进行 $m$ 次巡游，每次巡游会让 $x$ 变为 $p_x$。

求所有可能的 $p$ 进行 $m$ 次巡游后 $x$ 的和，对 $998244353$ 取模。

输入格式

本题有多组测试数据。

第一行输入 $1$ 个整数 $T$。

接下来 $T$ 行，每行输入 $3$ 个整数 $n,m,k$。

输出格式

共 $T$ 行，每行输出 $1$ 个整数，表示该组数据的答案。

6
3 5 3
114514 0 100000
501 1 249
9982443 231406890 1
9876543 735134400 421704
10000000 180957102 998140

12
616064221
532050777
653339286
829601668
778347084

提示

【样例解释】

对于第 $1$ 组测试数据，共有 $6$ 个可能的 $p$，下面列举出了所有可能的 $p$ 和对应的 $x$ 的变化。冒号前为 $p$，冒号后为 $p$ 对应的 $x$ 的变化。

• $[1,2,3]$：$3\to3\to3\to3\to3\to3$。
• $[1,3,2]$：$3\to2\to3\to2\to3\to2$。
• $[2,1,3]$：$3\to3\to3\to3\to3\to3$。
• $[2,3,1]$：$3\to1\to2\to3\to1\to2$。
• $[3,1,2]$：$3\to2\to1\to3\to2\to1$。
• $[3,2,1]$：$3\to1\to3\to1\to3\to1$。

答案为 $3+2+3+2+1+1=12$。

【数据范围】

本题采用捆绑测试。

• Subtask #1（$15\text{ pts}$）：$n\le6$，$m\le10^3$。
• Subtask #2（$20\text{ pts}$）：$m\le1$。
• Subtask #3（$20\text{ pts}$）：$k=1$。
• Subtask #4（$20\text{ pts}$）：$T=1$。
• Subtask #5（$25\text{ pts}$）：无特殊限制。

对于 $100\%$ 的数据，$1\le T\le10^3$，$1\le k\le n\le10^7$，$0\le m\le10^9$。