농장 분할

N×N 크기의 농지에 각 칸의 수익이 적혀 있다. 두 사람이 각각 축에 평행한 직사각형 영역을 받는다. 두 직사각형은 정확히 한 꼭짓점에서만 만나야 하며 (변을 공유하지 않음), 두 영역의 수익 합이 같아야 한다.

가능한 분할 방법의 수를 구하는 프로그램을 작성하시오.

입출력 예시

입력 1