페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5856
서브태스크

땅따먹기 (Land Division) 2초 1024MB

문제

JOI 국가는 세로 H 행, 가로 W 열의 격자 모양으로 구분 된 직사각형 형태를 하고 있다.

JOI 국가의 종 방향은 남북 방향에 평행하고 횡 방향은 동서 방향에 평행하다.

북쪽에서 i 행째 ( 1 ≤ i ≤ H ), 서쪽에서 j 열째 ( 1 ≤ j ≤ W )의 칸의 인구는 A_{ i, j}명이다.

JOI 국가에서는, 행정의 효율화를 위해, 다음의 조건을 만족하는 경계선을 1 개 이상 빼서,

나라 전체를 2 개 이상의 지구로 분할하기로 했다.

경계선은 격자 칸의 경계에 있다.

경계선은 JOI 국가의 북쪽 끝에서 남쪽 끝 또는 JOI 국가의 동쪽 끝에서 서쪽 끝을 연결하는 선분이다.

JOI 국가의 각 칸의 인구가 주어지므로 가능한 분할 방법 중

모든 지구의 인구가 같아지는 분할 방법은 몇 가지가 있는 지를 출력하는 프로그램을 작성하라.


입력

입력은 다음 형식으로 표준 입력에서 제공됩니다.

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 ≦ H ≦ 50．

1 ≦ W ≦ 50．

1 ≦ A_{i,j} ≦ 100\,000 (1 ≦ i ≦ H, 1 ≦ j ≦ W)．

모든 입력은 정수이다.


출력

표준 출력에 모든 지구의 인구가 같아지는 분할 방법은 몇 가지가 있는지를 한 줄로 출력하라 .


부분문제

번호 점수 조건
#112점

H=1

#226점

H ≤ 6 , W ≤ 6

#362점

추가 제약은 없다


예제1

입력
23
101020
101020
출력
3

아래 그림과 같이 모든 지구의 인구가 같아지는 분할 방법은  3가지가 있으므로 3을 출력한다.

이 입력 예는 작은 문제  2,3  의 제약 조건을 충족합니다.


예제2

입력
14
2112
출력
2

예제3

입력
33
294
753
618
출력
2

예제4

입력
11
10000
출력
0

출처

JOI 2022 예선2

역링크