题目描述

对于一个长为 $n$ 的非负整数序列 $\{a_i\}$，如果存在下标 $p$ 使得 $0 \le a_1 \le \ldots \le a_{p-1} \le a_p \ge a_{p+1} \ge \ldots \ge a_n \ge 0$，那么我们称 $\{a_i\}$ 是 单峰序列。例如 $[1,3,5,3,1],[1,1,1],[0,2,3],[100]$ 是单峰序列，而 $[3,1,3],[-1,1,0],[1,9,1,9]$ 不是。

Yuzu 有一个随机序列生成器，它会从所有的长为 $n$ 且元素总和为 $m$ 的单峰序列中，等概率地随机生成一个序列。Yuzu 会将生成的序列的每个元素的 $k$ 次幂求和，即，假设序列为 $\{a_i\}$，那么 Yuzu 会计算 $\sum a_i^k$。

Yuzu 想知道，她计算出的结果的期望值是多少。由于 Yuzu 是 OI 星球的居民，所以她只在乎答案对 $998244353$ 取模的值。换言之，假设答案为 $p/q$，你应当输出 $p \cdot q^{-1}$ 对 $998244353$ 取模的值，其中 $q^{-1}$ 是 $q$ 在模 $998244353$ 下的乘法逆元。

输入格式

第一行一个正整数 $T$，代表数据组数。

接下来 $T$ 行，每行三个整数 $n,m,k$，代表序列长度、序列的元素总和、Yuzu 的公式中的幂次。

输出格式

输出 $T$ 行，每行一个整数，代表期望值对 $998244353$ 取模的结果。

2
4 1 2
3 2 4

1
199648881

数据范围

• 对于 $30\%$ 的数据，$n,m \le 5$；
• 对于另外 $30\%$ 的数据，$k = 1$；
• 对于 $100\%$ 的数据，$1 \le T \le 10^6$，$1 \le n \le 10^3$，$1 \le m \le 10^3$，$1 \le k \le 10$。