Description

在一个名为"传送空间"的奇幻世界中，有 $n$ 个不同的传送门，编号为 $1$ 到 $n$ 。每个传送门 $i$ 都连接着另一个传送门 $p_i$。你是一名冒险者，初始时站在编号为 $k$ 的传送门前。接下来，你会进行 $m$ 次"传送"：每次传送时，你会从当前传送门 $x$ 传送到 $p_x$ 所指向的传送门。

现在你想知道在所有可能的传送门排列 $p$ 中（共有 $n!$ 种），经过 $m$ 次传送后，你所在的传送门编号 $x$ 的总和是多少？由于这个数字可能非常大，请对 $998244353$ 取模。

Format

Input

本题有多组测试数据。

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

接下来 $t$ 行，每行输入 $3$ 个整数$n$,$m$,$k$。（$1 \leq t \leq 10^3$，$1 \leq k \leq n \leq 10^7$，$0 \leq m \leq 10^9$）

Output

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

Samples

5
3 4 3
1 1 1
114514 0 1
1000000 1000000 1000000
9999999 12 98956

15
1
860922038
482511661
461235607

Limitation

1s, 1024KiB for each test case.