题目描述

JOI 国呈矩形，被划分为 $H$ 行 $W$ 列的网格状区域。JOI 国的纵向与南北方向平行，横向与东西方向平行。从北往南第 $i$ 行（$1 \le i \le H$）、从西往东第 $j$ 列（$1 \le j \le W$）的格子人口为 $A_{ij}$ 人。

为提升行政效率，JOI 国决定通过绘制一条或多条边界线，将全国划分为两个或以上的区域。边界线需满足以下条件：

• 边界线必须位于网格的边界上。
• 边界线必须是从 JOI 国北端到南端，或从东端到西端的连续线段。

已知 JOI 国每个格子的人口数，编写程序，计算在所有可能的划分方案中，能使各个区域人口相等的划分方法共有多少种。

输入格式

输入通过标准输入以如下格式给出：

$H$ $W$

$A_{1,1}$ $A_{1,2}$ $\cdots$ $A_{1,W}$

$A_{2,1}$ $A_{2,2}$ $\cdots$ $A_{2,W}$

$\vdots$

$A_{H,1}$ $A_{H,2}$ $\cdots$ $A_{H,W}$

输出格式

在标准输出中，以单行输出能使所有区域人口相等的划分方法的总数。

2 3
10 10 20
10 10 20

3

1 4
2 1 1 2

2

3 3
2 9 4
7 5 3
6 1 8

2

1 1
10000

0

提示

样例 1 解释

下图解释了样例 1 的三种方式：

:::align{center} :::

样例 2 解释

下图解释了样例 2 的两种方式：

:::align{center} :::

样例 3 解释

下图解释了样例 3 的两种方式：

:::align{center} :::

数据范围

• $1 \le H \le 50$。
• $1 \le W \le 50$。
• $1 \le A_{ij} \le 100\,000$（$1 \le i \le H$，$1 \le j \le W$）。
• 所有输入值均为整数。

子任务

1. （12 分）$H = 1$。
2. （26 分）$H \le 6$，$W \le 6$。
3. （62 分）无额外约束。

翻译由 Qwen3-235B 完成