003 - 国土分割

問題文

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)．
• 入力される値はすべて整数である．

小課題

1. (12 点) H = 1．
2. (26 点) H ≦ 6，W ≦ 6．
3. (62 点) 追加の制約はない．

採点に関する注意

すべての提出はジャッジシステム上で採点される．

提出されたソースコードは，小課題に対応するすべての採点用入力データについて正しい結果を返したとき，その小課題について正解と認められる．

各提出の得点は，提出されたソースコードについて正解と認められた小課題の得点の合計である．

この課題の得点は，この課題に対するすべての提出の得点の最大値である．

現在の得点は「提出結果」タブの「自分の得点状況」から確認できる．

入力

入力は以下の形式で標準入力から与えられる．
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,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 を出力する．

この入力例は小課題 2,3 の制約を満たす．

---

入力例 4
1 1
10000

出力例 4
0

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

この入力例はすべての小課題の制約を満たす．