#1814. 染色

    ID: 1814 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1455来源:qoj.ac数据:公开样例组合数学

染色

染色

题目描述

标题: 染色 - Problem - QOJ.ac

#7974. 染色

Statistics

The problem was used in the following contests:

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

输入格式

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

输出格式

输出一行一个整数,表示方案数 mod998244353 的结果。

样例一

input
3 3 5
output
9

样例二

input
500 1000 1000
output
928165755

数据范围

测试点编号N,MK1,2N×M≤203,4N×M≤1005,6N×M≤5000K≤1007,8N×M≤50009,10,11N×M≤10512,13N×M≤5×105K∈{N,M}14,15N×M≤5×105K≤100016,17,18,19,20N×M≤5×105

对于所有数据,保证 N,M 为正整数,0≤K≤N×M,对于所有编号为偶数的点,有 N=M。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 3 5
9

样例 2

500 1000 1000
928165755