题目描述

恶霸 Zhe 作恶多端，喜欢欺凌弱小。他的队友们长期遭受虐待。终于，他们决定不再忍受这位伙伴，逃往数字村，而恶霸紧追不舍。由于地形复杂且数字小径纵横交错，他们不易被抓住。

尽快熟悉地形对于这些无辜者逃脱欺凌的威胁至关重要。他们现在需要的就是统计数字村中数字小径的数量。

为简化问题，数字村被抽象为一个有 $n$ 行 $m$ 列的网格，格子中填有整数。一条数字小径是网格中满足下列条件的连续行走路径：

• 行走路径中相邻的格子共享一条公共边；
• 该行走路径是极大的，不能再被延伸；
• 该行走路径包含至少四个格子；
• 从一端走到另一端，任意两个相邻格子的值递增恰好为 $1$。

这里有一些例子。

:::align{center} :::

图 1 中的路径是无效的，因为其长度小于 $4$。

:::align{center} :::

图 2 中的路径是无效的，因为它不连续。

:::align{center} :::

图 3 中的路径是无效的，因为它可以被进一步延伸。

:::align{center} :::

图 4 中的路径也是无效的，因为路径中的值并未严格按 $1$ 递增。

:::align{center} :::

数字小径可以部分重叠。在图 5 中，有 $4$ 条用不同颜色标记的数字小径。

输入格式

第一行包含两个正整数 $n$ 和 $m$ ($1\le n,m\le 1000$)，描述网格的大小。

接下来的 $n$ 行，每行包含 $m$ 个整数，其中第 $j$ 个数记作 $a_{i,j}$ ($-10^7\le a_{i,j}\le 10^7$)，表示第 $i$ 行第 $j$ 列格子的值。

输出格式

输出数字小径的数量对 $(10^9+7)$ 取模的结果。

3 5
1 2 3 8 7
-1 -1 4 5 6
1 2 3 8 7

4

4 4
1 2 3 4
2 3 4 3
3 4 3 2
4 3 2 1

16

提示

翻译由 DeepSeek V4 Pro 完成