为了能在新学期获得 LoveLive! 的出场资格,$\mu's$ 的成员们必须所有考试都要及格才能继续活动。但高坂穗乃果的数学不太好,需要大家的帮助才能及格。
有一天,穗乃果碰到了一个这样的数学题,她不太会做,但是如果说自己不会做很可能会被希给予严厉的惩罚,所以她在 $\mu's$ 粉丝群中找到了学霸的你,希望能请你帮帮她。题目是这样的:
严厉的惩罚
给定一个 $n\times m$ 的 01 矩阵,记 $f_i$ 为恰有 $i$ 个 1 的子矩阵的个数,求:$\sum_{i=0}^{nm}i^2 \cdot f_i$
输出答案对 998244353 取模的结果。
第一行两个正整数 $n,m(1\le n,m \le 2000)$,表示矩阵的大小。
接下来 $n$ 行,每行$m$个为$0$或为$1$的字符。第$i$行的第$j$个字符代表矩阵的第$i$行的第$j$个元素的值。
仅一行一个非负整数表示答案对 998244353 取模的结果。
3 3 010 111 010
176
$f_0 = 4, f_1 = 17, f_2 = 4, f_3 = 6, f_4 = 4, f_5 = 1, ans = 0\times 4 + 1\times 17 + 4\times 4 + 9\times 6 + 16\times 4 + 25\times 1 = 176$