귀농

두 사람이 도시를 떠나 친구의 정사각형 농지에서 농사를 짓기로 했다. 농지의 크기는 N x N이고, 1 x 1 크기의 칸으로 나누어져 있다. 칸 (i, j)의 수익은 Aij이며, 이 값은 음수일 수도 있다.

친구는 두 사람에게 각각 비어 있지 않은 직사각형 모양의 땅을 하나씩 빌려주려고 한다. 각 직사각형의 변은 격자선과 평행해야 한다.

친구는 두 직사각형의 수익 합이 같도록 땅을 나누려 한다. 또한 두 땅이 변을 공유하지 않게 하면서 경쟁심을 유지하기 위해, 두 직사각형은 꼭짓점 하나에서만 만나야 한다. 두 직사각형은 겹치거나 변의 일부를 공유할 수 없다.

조건을 만족하는 두 직사각형을 고르는 방법의 수를 구하라. 두 사람을 서로 바꾸어 배정한 것은 새로운 방법으로 세지 않는다.

첫째 줄에 농지의 크기 N (1 <= N <= 50)이 주어진다.

다음 N개의 줄에는 각각 N개의 정수가 주어진다. i번째 줄의 j번째 정수는 칸 (i, j)의 수익 Aij이다 (-1000 < Aij < 1000).

조건을 만족하도록 두 직사각형을 빌려주는 방법의 수를 출력한다.

첫 번째 공개 테스트에서, 칸 좌표를 0부터 시작하고 직사각형의 양 끝점을 모두 포함한다고 하면 가능한 쌍은 다음과 같다.

• (0,0)-(1,1), (2,2)-(2,2)
• (1,0)-(1,0), (0,1)-(0,1)
• (2,0)-(2,0), (1,1)-(1,1)
• (1,1)-(1,1), (0,2)-(0,2)
• (2,1)-(2,1), (1,2)-(1,2)
• (2,0)-(2,1), (0,2)-(1,2)
• (1,0)-(2,0), (0,1)-(0,2)