该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

A国的国土形状类似于H*W的矩形，矩形中每个单元格上的数字表示该区域的人口。

为了提高行政效率，通过划定满足以下条件的边界线，将整个国家划分为多个地区。

• 边界线是从A国的北部边缘到南部边缘的线或从A国的东部边缘到西部边缘的线。

现给出A国每个地区的人口，请创建一个程序以找出有多少种可能的划分方法，使得所有地区的人口相

等.

Format

Input

第一行输入两个整数H W,表示矩阵的大小

接下来H行W个整数，第 i 行 第 j 个整数表示(i,j)区域的人口$A_{i,j}$

Output

输出一行一个整数，有多少种可能的划分方法，使得所有地区的人口相等。

Samples

2 3 
10 10 20 
10 10 20

3

3 3 
2 9 4 
7 5 3 
6 1 8

2

hint

样例1解释： 如下图所示，有不同的划分方式，使所有地区的人口相等。

Limitation

约束

数据范围

• $1\leq H \leq 50$

• $1\leq W \leq50$

• $1\leq A_{i,j} \leq 100000$

  | 种类 | 分值 | 约束 | | :--- | ---: | :--: | | 1 | 20 | H=1 | | 2 | 30 | $H,W\leq 6$| | 3 | 50 | 没有其他限制 |