1452: #6275. 棋盘

Memory Limit：512 MB Time Limit：2.000 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

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

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

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

输入格式

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

输出格式

一个整数，答案对 998244353998244353998244353 取膜的结果。

样例

输入样例 1

2 3 2

输出样例 1

21

输入样例 2

2 10 7

输出样例 2

7914

输入样例 3

3 9 6

输出样例 3

13876624

样例解释 1

如果把白子视作 000 ，黑子视作 111 ，则所有可能的方案有 212121 种，分别为

010 001 101 100 101 110 100
001 010 000 001 001 001 010

100 101 001 000 001 010 011
011 011 100 101 101 100 100

011 001 101 100 101 110 101
101 110 100 101 101 101 110

样例解释 2, 3

那么多种，写不下。

数据范围与提示

对于所有数据，NNN , MMM 为正整数， 1≤N≤31 \le N \le 31≤N≤3 ， 0≤K≤N×M 0 \le K \le N \times M 0≤K≤N×M 。

当 N=1 N = 1 N=1 时， 1≤M≤105 1 \le M \le 10^5 1≤M≤10​5​​ 。

当 N=2 N = 2 N=2 时， 1≤M≤5×104 1 \le M \le 5\times 10^4 1≤M≤5×10​4​​ 。

当 N=3 N = 3 N=3 时， 1≤M≤104 1 \le M \le 10^4 1≤M≤10​4​​ 。

本题采用打包测试。

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

Subtask 编号 NNN MMM KKK 其他限制 该 Subtask 分值
0 N×M≤15N \times M \le 15 N×M≤15 5
1 =1= 1=1 ≤1000 \le 1000 ≤1000 6
2 =2= 2=2 ≤1000 \le 1000 ≤1000 9
3 =3= 3=3 ≤1000 \le 1000 ≤1000 13
4 =1= 1=1 17
5 M×K≤106 M \times K \le 10^{6} M×K≤10​6​​ 19
6 31
SubmitSubmit RecordStatisticsShowOff!