国土分割 (Land Division)

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

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

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

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

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

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

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

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

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

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

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

JOI 2022 · JCIOI · CC BY-SA 4.0

入力は以下の形式で標準入力から与えられる．

\(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}\)

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