C1938 [Wannafly冬令营2018Day8]穗乃果的考试(简单版)

内存限制:512 MB 时间限制:1000 ms

题目描述

为了能在新学期获得 LoveLive! 的出场资格,$\mu's$ 的成员们必须所有考试都要及格才能继续活动。但高坂穗乃果的数学不太好,需要大家的帮助才能及格。

有一天,穗乃果碰到了一个这样的数学题,她不太会做,但是如果说自己不会做很可能会被希给予严厉的惩罚,所以她在 $\mu's$ 粉丝群中找到了学霸的你,希望能请你帮帮她。题目是这样的:

给定一个 $n\times m$ 的 01 矩阵,记 $f_i$ 为恰有 $i$ 个 1 的子矩阵的个数,求:$\sum_{i=0}^{nm}i \cdot f_i$

输出答案对 998244353 取模的结果。

输入格式

第一行两个正整数 $n,m(1\le n,m \le 2000)$,表示矩阵的大小。

接下来 $n$ 行,每行$m$个为$0$或为$1$的字符。第$i$行的第$j$个字符代表矩阵的第$i$行的第$j$个元素的值。

输出

仅一行一个非负整数表示答案对 998244353 取模的结果。

样例

样例输入 1

3 3 010 111 010

样例输出 1

64

提示