UOJ Logo Universal Online Judge

UOJ

附件下载 统计

《比托邦》(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$。

子任务编号 $\sum n\le $ 特殊性质 分值
$1$ $4$ $5$
$2$ $8$ $10$
$3$ $20$ $m=n-1$ $5$
$4$ $500$ $10$
$5$ $5000$ $10$
$6$ $2\cdot 10^5$ $15$
$7$ $10^5$ $m\ge n-5$ $10$
$8$ $500$ $10$
$9$ $5000$ $10$
$10$ $2\cdot 10^5$ $15$

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

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