#6516. 「雅礼集训 2018 Day11」进攻!

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

你将向敌方发起进攻!敌方的防御阵地可以用一个 N×M 01 矩阵表示,标为 1 的表示有效区域,标为 0 的是敌人的预警装置。

你将发起 K 轮进攻,每一轮从所有 \frac{NM(N+1)(M+1)}{4} 种可能中选定一个矩形区域对其进行轰炸。如果 K 轮后存在一个有效区域每次都被轰炸到,并且没有一次触发敌人的预警装置,那么将对敌人造成致命打击。现在你想知道一共有多少种不同的轰炸方案能对敌人造成致命打击,输出对 998244353 取模的结果。

输入格式

第一行三个数 N, M, K

接下来 K 行每行一个长度为 M 01 串表示敌方的防御阵地。

输出格式

一个数表示答案。

样例

样例输入 1

2 3 2
011
110

样例输出 1

23

数据范围与提示

测试点编号 N, M \leq K \leq
1 4
2 10 2
3 100
4
5 1000
6 4 10^6
7 10
8 100
9 1000
10 2000 10