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.

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

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.

For all cases: $1\le T\le10^3$, $1\le k\le n\le 10^7$, $0\le m\le10^9$.