Problem Statement
继杰克逊·波洛克和克利福德·斯蒂尔之后,亚当决定创作一些抽象艺术。他决定从简单的开始:画一幅由三颗星星组成的画。
亚当买了一张精致的纸,它可以被看作是一个由 $n$ 行和 $m$ 列组成的网格。亚当指定了一些适合画星星的格子。
由于这张纸很大,亚当需要先切出绘画所需的部分。它可以是网格的任何子矩形。形式化地,对于整数 $x_1,x_2,y_1,y_2$,如果 $0\le x_1\le x_2< n$ 和 $0\le y_1\le y_2 < m$,行编号在 $[x_1,x_2]$ 且列编号在 $[y_1,y_2]$ 的单元格构成一个子矩形。这些是全部的子矩形。然后,亚当需要在子矩形中找到三个不同的格子来绘制星星。当然,这些单元格应该被指定为适合画星星。
亚当想知道他有多少种方法来创造这样的艺术品。由于这个数字可能相当大,你只需要输出它对 $10^9+7$ 取余的结果。
Implementation Details
你应该包含 art.h,并实现如下过程:
int count(bool[][] v)
- $v$: 一个二维数组,大小为 $n\times m$。对于每个 $i,j$($0\le i\le n-1$, $0\le j\le m-1$),$v[i][j]=1$ 如果第 $i$ 行第 $j$ 列能画星星,否则 $v[i][j]=0$。
- 你实现的过程会被调用恰好一次。
- 你应该返回创造艺术品的方案数对 $10^9+7$ 取余的值:一个 $[0,10^9+6]$ 的整数。
Example
考虑如下调用:count([[1,1,0],[1,0,0]])
我们只能在其中的三个格子中画出星星,而且有两个不同的子矩形包含这三个星星。因此,有两种不同的创造艺术品的方法,一个正确的程序应该返回 $2$。
Constraints
$1\le n,m\le 3000$
Subtasks
- (20 分)$n,m\le 80$
- (20 分)$n,m\le 300$
- (20 分)所有格子都可以画星星。
- (40 分)无特殊限制。
Sample Grader
样例交互器以下列格式读取输入。
- 第一行:$n~m$
- 接下来 $n$ 行每行 $m$ 个 0 或 1 的字符,描述 $v$
样例交互器以下列格式打印你的输出。
- 一行,你的返回值