상근이와 선영이는 도심 속의 삶에 싫증을 느꼈고, 친구 현수가 있는 시골로 농사를 지으려 내려왔다. 현수의 땅은 크기가 N×N 인 정사각형이고, 땅은 단위 정사각형 1×1로 나누어져 있다. 각 단위 정사각형 (i,j)의 수익은 A_ij이다. A_ij는 음수가 될 수도 있다. (땅을 경작하지 않아 관리가 필요한 경우)

현수는 자신의 땅의 일부를 상근이와 선영이에게 빌려주려고 한다. 두 사람이 받게되는 땅은 항상 직사각형 모양이고, 변은 축에 평행하다.

현수는 두 사람이 농사지을 땅의 수익의 합이 같게 되도록 땅을 빌려주려고 한다. 또, 경쟁심을 유도하기위해 두 땅은 꼭짓점 하나에서만 만나게 하려고 한다. (변을 공유할 수는 없다)

현수 땅의 정보가 주어졌을 때, 땅을 나누어주는 방법의 수를 구하는 프로그램을 작성하시오. 

입력 형식

첫째 줄에 땅의 크기 N (1 ≤ N ≤ 50)이 주어진다.

다음 N개의 줄의 N번째 숫자 A_ij는 부분 정사각형 (i,j)의 수익이다. (-1000 < A_ij < 1000)

출력 형식

현수의 조건을 만족시키면서 땅을 빌려주는 방법의 수를 출력한다.

예제 입력 1

3
1 2 3
2 3 4
3 4 8

예제 출력 1

7

예제 입력 2

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

예제 출력 2

10

예제 입력 3

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

예제 출력 3

36

힌트

가능한 방법은 다음과 같다.

• (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)