国土分割 (Land Division)

問題文

JOI 国は縦 H 行，横 W 列のマス目状に区切られた長方形の形をしている．JOI 国の縦方向は南北方向に平行であり，横方向は東西方向に平行である．北から i 行目 (1 ≦ i ≦ H)，西から j 列目 (1 ≦ j ≦ W) のマスの人口は A_i,j 人である．

JOI 国では，行政の効率化のため，次の条件を満たす境界線を 1 本以上引くことで，国全体を 2 つ以上の地区に分割することにした．

• 境界線はマス目の境界上にある．
• 境界線は JOI 国の北端から南端または JOI 国の東端から西端を結ぶ線分である．

JOI 国の各マスの人口が与えられるので，考えられる分割方法のうち，すべての地区の人口が等しくなるような分割の方法は何通りあるかを求めるプログラムを作成せよ．

制約

• 1 ≦ H ≦ 50．
• 1 ≦ W ≦ 50．
• 1 ≦ A_i,j ≦ 100 000 (1 ≦ i ≦ H，1 ≦ j ≦ W)．
• 入力される値はすべて整数である．

入力

入力は以下の形式で標準入力から与えられる．
H W
A_1,1 A_1,2 … A_1,W
A_2,1 A_2,2 … A_2,W
:
A_H,1 A_H,2 … A_H,W

出力

標準出力に，すべての地区の人口が等しくなるような分割の方法は何通りあるかを 1 行で出力せよ．

入出力例

入力例 1

2 3
10 10 20
10 10 20

出力例 1

3

下図のように，すべての地区の人口が等しくなるような分割の方法は 3 通りあるため，3 を出力する．

入力例 2

1 4
2 1 1 2

出力例 2

2

下図のように，すべての地区の人口が等しくなるような分割の方法は 2 通りあるため，2 を出力する．

入力例 3

3 3
2 9 4
7 5 3
6 1 8

出力例 3

2

下図のように，すべての地区の人口が等しくなるような分割の方法は 2 通りあるため，2 を出力する．

入力例 4

1 1
10000

出力例 4

0

すべての地区の人口が等しくなるような分割の方法は存在しないため，0 を出力する．

---