시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 248 100 72 43.902%

문제

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

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

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

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

입력

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

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

출력

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

예제 입력

3
1 2 3
2 3 4
3 4 8

예제 출력

7

힌트

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

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