题目背景

今夜星光闪闪 我爱你的心满满 ……

题目描述

天空中有一个包含 $n$ 颗星星的星团。

小 K 认为天空中只有一个星团不够浪漫，因此她准备施展魔法。若在她施展魔法前第 $i$ 个星团包含 $a_i$ 颗星星，且 $a_i\ge2$；则施展魔法后天空中分别增加包含 $1\sim a_i-1$ 颗星星的星团（注意原本的星团会被保留）。

小 K 定义一个包含 $v$ 颗星星的星团的闪耀度为 $k^v$。求她施展 $m$ 次魔法后，天空中所有星团的闪耀度之和，对 $998244353$ 取模。

---

【形式化题意】

给定一个可重集 $S_0$，初始 $S_0$ 中只有一个数 $n$。

定义一次操作为：新建一个可重集 $S_1$，对于 $\forall1\le i\le|S_0|$，若 $S_{0,i}\ge 2$，则对于 $\forall1\le j\le S_{0,i}-1$，将 $j$ 加入 $S_1$。在这次操作的最后，将 $S_1$ 中所有元素加入 $S_0$。

求进行了 $m$ 次操作后的 $\sum_{i=1}^{|S_0|} k^{S_{0,i}}$，对 $998244353$ 取模。

输入格式

本题有多组测试数据。

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

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

输出格式

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

5
3 4 6
8 2 5
501 501 6
11451 41919 313172124
824431 960532 10000007

420
610340
520860091
95420244
42443525

提示

【样例解释】

以下记 $L_i$ 表示包含 $i$ 颗星星的星团的个数，即 $S_{0,j}=i$ 的个数。

第 $1$ 组测试数据中：

• 第一次施展魔法（进行操作）后 $L_1=1,L_2=1,L_3=1$。
• 第二次施展魔法（进行操作）后 $L_1=3,L_2=2,L_3=1$。
• 第三次施展魔法（进行操作）后 $L_1=6,L_2=3,L_3=1$。
• 第四次施展魔法（进行操作）后 $L_1=10,L_2=4,L_3=1$。

因此答案为 $10\times6^1+4\times6^2+1\times6^3=420$。

第 $2$ 组测试数据中：

• 第一次施展魔法（进行操作）后 $\forall1\le i\le n,L_i=1$。
• 第二次施展魔法（进行操作）后 $\forall1\le i\le n,L_i=n-i+1$。

因此答案为 $\sum_{i=1}^n(n-i+1)5^i=610340$。

【数据范围】

本题采用捆绑测试。

记 $\sum n,\sum m$ 分别为单个测试点内 $n,m$ 的和。

• Subtask #1（$5\text{ pts}$）：$k=0$。
• Subtask #2（$10\text{ pts}$）：$n\le5$ 且 $m\le5$。
• Subtask #3（$10\text{ pts}$）：$m\le3$。
• Subtask #4（$10\text{ pts}$）：$k=1$。
• Subtask #5（$10\text{ pts}$）：$n\le2\times10^2$ 且 $m\le2\times10^2$ 且单个测试点内的 $k$ 相等。
• Subtask #6（$10\text{ pts}$）：$n\le2\times10^3$ 且 $m\le2\times10^3$ 且单个测试点内的 $k$ 相等。
• Subtask #7（$15\text{ pts}$）：$\sum n\le2\times10^7$。
• Subtask #8（$15\text{ pts}$）：$\sum m\le2\times10^6$。
• Subtask #9（$15\text{ pts}$）：无特殊限制。

对于 $100\%$ 的数据，$1\le T\le5\times10^5$，$1\le n\le2\times10^6$，$1\le m\le2\times10^6$，$\sum m\le2\times10^7$，$0\le k\le998244352$。

本题 IO 量较大，请采用较快的 IO 方式。