농장 분할

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

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

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 50) 둘째 줄부터 N개의 줄에 N개의 정수가 주어진다.

출력

분할 방법의 수를 출력한다.

입출력 예시

입력 1

3
1 2 3
2 3 4
3 4 8

출력 1

7