QOJ.ac

QOJ

Time Limit: 5 s Memory Limit: 1024 MB Total points: 100

# 7974. 染色

统计

给定一个 $ N \times M $ 的网格图,每个格子初始为白色,现在需要将 $ K $ 个格子染成黑色,使得每行每列的黑格子数均为奇数,求方案数。

输入格式

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

输出格式

输出一行一个整数,表示方案数 $ \bmod 998244353 $ 的结果。

样例一

input
3 3 5
output
9

样例二

input
500 1000 1000
output
928165755

数据范围

测试点编号$ N,M $$ K $
$ 1,2 $$ N \times M \le 20 $
$ 3,4 $$ N \times M \le 100 $
$ 5,6 $$ N \times M \le 5000 $$ K \le 100 $
$ 7,8 $$ N \times M \le 5000 $
$ 9,10,11 $$ N \times M \le 10^5 $
$ 12,13 $$ N \times M \le 5 \times 10^5 $$ K \in \{N,M\} $
$ 14,15 $$ N \times M \le 5 \times 10^5 $$ K \le 1000 $
$ 16,17,18,19,20 $$ N \times M \le 5 \times 10^5 $

对于所有数据,保证 $ N,M $ 为正整数,$ 0 \le K \le N \times M $,对于所有编号为偶数的点,有 $ N=M $。