《比托邦》(Bitopia) 是由比特智慧 (Bitwise) 自主研发的一款模拟经营游戏。该游戏中，玩家需在一张比特地图上简单规划，逐步搭建心目中的比特国特色乌托邦 —— 比托邦。

游戏初，地图上仅有一堵呈正 $n$ 边形的围墙，其每条边的中点处各有一个向内的“接口”。玩家需按照要求铺设恰好 $m$ 条“道路”：每次用直线段连接任意两个未使用的接口，在不与已有道路交叉的情况下铺设一条可视为无限窄的道路，并于其中点处两侧各生成一个新的接口。下图描述了 $n = 6$ 时的一次正确铺设和两种错误铺设。

此时邦内被道路划分为了 $m+1$ 个“区域”。每个区域将具备 $k$ 种“功能”之一，分别以居住区、工业区、旅游区等模式发展。为了提升用地效率，玩家应赋予各区域一种功能，使得相邻的区域功能不同。下图（所有接口均已略去）描述了 $n = 6$, $m = 4$ 时的一种正确规划和一种错误规划。

比托邦的规划完工后，游戏则进入下一进程。作为重度网瘾少年，亚砜蚤 (Sulflea) 想知道对于给定的 $n,m,k$ 规划完工后能呈现多少不同的比托邦。请你帮他求出对 $998244353$ 取模后的答案。规划的过程并不重要：两个结果视为不同，当且仅当不进行任何旋转或对称变换时，一结果中存在一条道路未在另一结果中出现，或两者铺设情况相同但存在同个区域于两者中功能不同。多条不同时间铺设而恰巧共线的道路不会自动合并成一整条。

输入格式

请注意，每个测试点中包含一组或多组数据。

输入的第一行包含一个整数 $T$，表示数据组数。

接下来 $T$ 行，每行包含三个整数 $n, m, k$，给出一组数据。

输出格式

对于每组数据，输出一行一个整数，表示能规划出的不同结果数，对 $998244353$ 取模。

样例一

input

1
3 2 3

output

18

样例二

input

1
5 3 5

output

15200

样例三

input

4
10 9 573830125
24 9 407166302
365 360 196185453
512 511 726048849

output

55553052
59173083
92026983
81790841

数据范围

对于所有数据，$3 \le n \le 2 \cdot 10^5$, $1 \le m < n$, $3 \le k < 998244353$。

时间限制：$2\texttt{s}$

空间限制：$512\texttt{MB}$