UOJ Logo Universal Online Judge

UOJ

#485. 【UR #18】没这种事

附件下载 统计

成为鸽王的三个要求之二,优秀的找借口水平。

众所周知,咕咕咕时找的借口不能相似,否则虽然咕掉了事情,但是很有可能因此被人挂起来*。

例如蚂蚁国的代表选手就犯下了重大失误,在某次交互中给出了两个相似的借口,被主持人判了违规。那两个借口看上去差别很大,然而主持人很快就发现,只要进行几次魔改,这两个借口就会变的完全一样。

具体来说,每个借口都可以对应一个 $n\times m$ 的矩阵,且矩阵的每个元素都是不大于 $k$ 的正整数。将一个借口的对应矩阵进行左右翻转某一行或者上下翻转某一列的操作,被称为是对这个借口的一次魔改。

如果一个借口进行若干次魔改后,和另一个借口的对应矩阵完全相同,则称这两个借口是相似的。

主持人突然想要考考码农同学,有多少个有序借口对 $(S,T)$ 满足 $S$ 和 $T$ 是相似的。码农同学仅仅精通找不相似的借口,对这种数数问题自然一无所知,因此来求助你。由于答案可能很大,请对 $998244353$ 取模。

输入格式

输入共一行,包含三个正整数 $ n, m, k $ 。

输出格式

输出共一行一个非负整数,表示答案。

样例一

input

2 2 2

output

70

样例二

input

2 3 2

output

420

样例三

input

5 5 3

output

985619174

样例四

input

5 233 99824435

output

461607324

样例五

input

8 9 72

output

690487734

限制与约定

对于 $ 100 \% $ 的数据,$ 1 \le n \times m \le 5 \times 10^5, 1 \le k < 998244353 $ 。 下表是更详细的数据范围,表中留空代表无特殊限制。

子任务编号$n$$n \times m$$k$分值
$1$$\le 15$$\le 5$$5$
$2$$\le 3$$8$
$3$$\le 80$$10$
$4$$\le 5000$$22$
$5$$\le 5$$20$
$6$$35$

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

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

下载

样例数据下载