프로그램 명: coci_ratar
제한시간: 1 초

[요약] 미르코와 슬라브코는 주어진 정사각형 모양의 땅을 얻을 수 있는 이익이 같게 두 직사각형을 만들어 서로 하나씩 가져가려고 합니다. 그런데 둘은 서로 감시를 할 수 있기 위해 한 모서리가 서로 맞닿은 두 직사각형을 만들려고 합니다. 전부해서 몇 가지 방법이 있는지 출력하세요.

After Mirko's failed stint as a coach and a passing obsession with Croatian meat delicacies, his weight problems have motivated him to work hard as a farmer. He has moved to a village where his friend Slavko lives. Farmers in the village share a large common plot of land in the shape of a N×N square, divided into N² unit squares. A unit square at coordinates (i, j) brings in the income of Aij, which can be negative (for example, if the square has to be maintained but is not cultivated). The farmers always divide the common land into smaller rectangular fields with edges parallel to the common land edges.

Slavko is skeptical of Mirko since his failure as a coach, so he insists that both of them are assigned land with the same total income, but also thet the two plots share exactly one common corner so that the two friends can keep an eye on each other (Slavko knows that Mirko is prone to mischief). The common corner must be the only point where the two plots meet, in order to prevent border-related arguments.

You are given a description of the common land plot. Find the total number of plot pairs that satisfy Slavko's criteria.

입력

The first line of input contains the positive integer N (1 ≤ N ≤ 50), the dimensions of the common land plot.

Each of the following N lines contains N space-separated numbers Aij (-1000 < Aij < 1000), the income provided by the respective cell.

출력

The first and only line of output must contain the totl number of plot pairs satisfying the given condition.

입출력 예

input 

3 
1 2 3 
2 3 4 
3 4 8 

output 

7 

input 

4 
-1 -1 -1 -1 
1 2 3 4 
1 2 3 4 
1 2 3 4 

output 

10

input 

5 
-1 -1 -1 -1 -1 
-2 -2 -2 -2 -2 
-3 -3 -3 -3 -3 
-4 -4 -4 -4 -4 
-5 -5 -5 -5 -5 

output 

36 

Clarification of the first example: The possible rectangle pairs are: 

(0,0)-(1,1) and (2,2)-(2,2), (1,0)-(1,0) and (0,1)-(0,1), (2,0)-(2,0) and (1,1)-(1,1), (1,1)-(1,1) and (0,2)-(0,2), 
(2,1)-(2,1) and (1,2)-(1,2), (2,0)-(2,1) and (0,2)-(1,2), (1,0)-(2,0) and (0,1)-(0,2). 

출처:coci/2013-2014/contest1
번역:ladown21
[질/답] [제출 현황] [푼 후(1)]
[ 채 점 ] [홈으로]  [뒤 로]