P13280 Midnight Go Round
Description
There is a **permutation** $p$ of length $n$ (each integer from $1$ to $n$ appears exactly once in $p$) and a variable $x$, initially set to $k$.
You need to perform $m$ operations, where each operation updates $x$ to $p_x$.
Find the sum of all possible values of $x$ after $m$ operations, considering all possible permutations $p$, modulo $998244353$.
Input Format
**This problem contains multiple test cases.**
The first line contains an integer $T$.
Each of the next $T$ lines contains three integers $n$, $m$, $k$.
Output Format
Output $T$ lines, each containing one integer representing the answer for the corresponding test case.
Explanation/Hint
### Sample Explanation
For the first test case:
- All possible permutations $p$ and their corresponding $x$ sequences:
- $[1,2,3]$: $3→3→3→3→3→3$
- $[1,3,2]$: $3→2→3→2→3→2$
- $[2,1,3]$: $3→3→3→3→3→3$
- $[2,3,1]$: $3→1→2→3→1→2$
- $[3,1,2]$: $3→2→1→3→2→1$
- $[3,2,1]$: $3→1→3→1→3→1$
- Final answer: $3+2+3+2+1+1=12$.
### Constraints
**This problem uses bundled testing.**
| Subtask | Score | Constraints |
|---------|-------|-------------|
| #1 | 15 pts | $n\le6$, $m\le10^3$ |
| #2 | 20 pts | $m\le1$ |
| #3 | 20 pts | $k=1$ |
| #4 | 20 pts | $T=1$ |
| #5 | 25 pts | No additional constraints |
For all cases: $1\le T\le10^3$, $1\le k\le n\le 10^7$, $0\le m\le10^9$.