题目描述

给你一个 $n \times m$ 的二进制矩阵 $mat$ ，请你返回有多少个 子矩形 的元素全部都是 1 。

输入格式

第一行两个整数 $n$ 和 $m$，表示行和列；

接下来的 $n$ 行，每行 $m$ 个 0 或 1 的数。

输出格式

一行一个整数表示答案，答案可能会很大，请对答案模 $10^9 + 7$后输出。

样例

示例 1：

3 3
1 0 1
1 1 0
1 1 0

13

解释：

有 6 个 1x1 的矩形。

有 2 个 1x2 的矩形。

有 3 个 2x1 的矩形。

有 1 个 2x2 的矩形。

有 1 个 3x1 的矩形。

矩形数目总共 = 6 + 2 + 3 + 1 + 1 = 13 。

示例 2：

3 4
0 1 1 0
0 1 1 1
1 1 1 0

24

解释：

有 8 个 1x1 的子矩形。

有 5 个 1x2 的子矩形。

有 2 个 1x3 的子矩形。

有 4 个 2x1 的子矩形。

有 2 个 2x2 的子矩形。

有 2 个 3x1 的子矩形。

有 1 个 3x2 的子矩形。

矩形数目总共 = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24 。

提示：

• $1 <= m, n <= 1000$
• $mat[i][j]$ 仅包含 $0$ 或 $1$

source

leetcode.cn 1504. 统计全 1 子矩形 数据范围与原题有改动。