국토 분할

문제

JOI 국은 세로 $H$ 행, 가로 $W$ 열의 격자 모양으로 나뉜 직사각형 모양을 하고 있다. JOI 국의 세로 방향은 남북 방향과 평행하고, 가로 방향은 동서 방향과 평행하다. 북쪽에서 $i$ 번째 행 ($1 \le i \le H$), 서쪽에서 $j$ 번째 열 ($1 \le j \le W$) 인 칸의 인구는 $A_{i,j}$ 명이다.

JOI 국에서는 행정의 효율화를 위해, 다음 조건을 만족하는 경계선을 $1$ 개 이상 그어 나라 전체를 $2$ 개 이상의 지구로 분할하기로 했다.

• 경계선은 격자의 경계 위에 있다.
• 경계선은 JOI 국의 북쪽 끝에서 남쪽 끝을 잇거나, JOI 국의 동쪽 끝에서 서쪽 끝을 잇는 선분이다.

JOI 국의 각 칸의 인구가 주어질 때, 가능한 분할 방법 중 모든 지구의 인구가 같아지는 분할 방법이 몇 가지인지 구하는 프로그램을 작성하시오.

제한

• $1 \le H \le 50$.
• $1 \le W \le 50$.
• $1 \le A_{i,j} \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$ 점) 추가 제약이 없다.

입력

입력은 다음 형식으로 표준 입력에서 주어진다.
$H$ $W$
$A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,W}$
$A_{2,1}$ $A_{2,2}$ $\dots$ $A_{2,W}$
$:$
$A_{H,1}$ $A_{H,2}$ $\dots$ $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$ 을 출력한다.

이 예제는 모든 서브태스크의 제약을 만족한다.