题目描述

NiroBC 姐姐有一个漂亮的大棋盘，棋盘的长和宽分别是 $N$ 和 $M$ ，有 $N\times M$ 个格子。NiroBC 姐姐有无限数量的黑，白两种颜色的棋子，她关心的是，如果每个格子都放上恰好一个棋子，那么所有可能的局面当中，所有黑子构成的联通块数量正好为 $K$ 的局面有多少种。

两个局面被视为不同，当且仅当存在一个位置，在这两个局面中放了不同的棋子。

两个格子被视为相连，当且仅当它们有一条公共边，且它们的棋子同色。

输入格式

一行，三个整数，$N, M, K$ 。

输出格式

一个整数，答案对 $998244353$ 取模的结果。

2 3 2

21

2 10 7

7914

3 9 6

13876624

数据范围与提示

对于所有数据，$N$ , $M$ 为正整数， $1 \le N \le 3$ ， $0 \le K \le N \times M$ 。

当 $N = 1$ 时， $1 \le M \le 10^5$ 。

当 $N = 2$ 时， $1 \le M \le 5\times 10^4$ 。

当 $N = 3$ 时， $1 \le M \le 10^4$ 。

本题采用打包测试。

各个 Subtask 的特殊限制如下，不填代表该项无特殊限制。