시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 376 145 107 41.473%

문제

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

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

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

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

입력

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

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

출력

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

예제 입력 1

3
1 2 3
2 3 4
3 4 8

예제 출력 1

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)
W3sicHJvYmxlbV9pZCI6IjExODQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkYzBcdWIxOGQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YzY0MCBcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHViM2M0XHVjMmVjIFx1YzE4ZFx1Yzc1OCBcdWMwYjZcdWM1ZDAgXHVjMmViXHVjOTlkXHVjNzQ0IFx1YjI5MFx1YWYwOFx1YWNlMCwgXHVjZTVjXHVhZDZjIFx1ZDYwNFx1YzIxOFx1YWMwMCBcdWM3ODhcdWIyOTQgXHVjMmRjXHVhY2U4XHViODVjIFx1YjE4ZFx1YzBhY1x1Yjk3YyBcdWM5YzBcdWM3M2NcdWI4MjQgXHViMGI0XHViODI0XHVjNjU0XHViMmU0LiBcdWQ2MDRcdWMyMThcdWM3NTggXHViNTQ1XHVjNzQwIFx1ZDA2Y1x1YWUzMFx1YWMwMCBOJnRpbWVzO04gXHVjNzc4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc3NFx1YWNlMCwgXHViNTQ1XHVjNzQwIFx1YjJlOFx1YzcwNCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgMSZ0aW1lczsxXHViODVjIFx1YjA5OFx1YjIwNFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWIyZThcdWM3MDQgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IChpLGopXHVjNzU4IFx1YzIxOFx1Yzc3NVx1Yzc0MCBBPHN1Yj5pajxcL3N1Yj5cdWM3NzRcdWIyZTQuIEE8c3ViPmlqPFwvc3ViPlx1YjI5NCBcdWM3NGNcdWMyMThcdWFjMDAgXHViNDIwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIChcdWI1NDVcdWM3NDQgXHVhY2JkXHVjNzkxXHVkNTU4XHVjOWMwIFx1YzU0YVx1YzU0NCBcdWFkMDBcdWI5YWNcdWFjMDAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YWNiZFx1YzZiMCk8XC9wPlxyXG5cclxuPHA+XHVkNjA0XHVjMjE4XHViMjk0IFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWI1NDVcdWM3NTggXHVjNzdjXHViZDgwXHViOTdjIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YzY0MCBcdWMxMjBcdWM2MDFcdWM3NzRcdWM1ZDBcdWFjOGMgXHViZTRjXHViODI0XHVjOGZjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViNDUwIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWJjMWJcdWFjOGNcdWI0MThcdWIyOTQgXHViNTQ1XHVjNzQwIFx1ZDU2ZFx1YzBjMSBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHViYWE4XHVjNTkxXHVjNzc0XHVhY2UwLCBcdWJjYzBcdWM3NDAgXHVjZDk1XHVjNWQwIFx1ZDNjOVx1ZDU4OVx1ZDU1OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNjA0XHVjMjE4XHViMjk0IFx1YjQ1MCBcdWMwYWNcdWI3OGNcdWM3NzQgXHViMThkXHVjMGFjXHVjOWMwXHVjNzQ0IFx1YjU0NVx1Yzc1OCBcdWMyMThcdWM3NzVcdWM3NTggXHVkNTY5XHVjNzc0IFx1YWMxOVx1YWM4YyBcdWI0MThcdWIzYzRcdWI4NWQgXHViNTQ1XHVjNzQ0IFx1YmU0Y1x1YjgyNFx1YzhmY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YjYxMCwgXHVhY2JkXHVjN2MxXHVjMmVjXHVjNzQ0IFx1YzcyMFx1YjNjNFx1ZDU1OFx1YWUzMFx1YzcwNFx1ZDU3NCBcdWI0NTAgXHViNTQ1XHVjNzQwIFx1YWYyZFx1YzlkM1x1YzgxMCBcdWQ1NThcdWIwOThcdWM1ZDBcdWMxMWNcdWI5Y2MgXHViOWNjXHViMDk4XHVhYzhjIFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIChcdWJjYzBcdWM3NDQgXHVhY2Y1XHVjNzIwXHVkNTYwIFx1YzIxOFx1YjI5NCBcdWM1YzZcdWIyZTQpPFwvcD5cclxuXHJcbjxwPlx1ZDYwNFx1YzIxOCBcdWI1NDVcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YjU0NVx1Yzc0NCBcdWIwOThcdWIyMDRcdWM1YjRcdWM4ZmNcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViNTQ1XHVjNzU4IFx1ZDA2Y1x1YWUzMCBOICgxICZsZTsgTiAmbGU7IDUwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1Yzc1OCBOXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MCBBPHN1Yj5pajxcL3N1Yj5cdWIyOTQgXHViZDgwXHViZDg0IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSAoaSxqKVx1Yzc1OCBcdWMyMThcdWM3NzVcdWM3NzRcdWIyZTQuICgtMTAwMCAmbHQ7IEE8c3ViPmlqPFwvc3ViPiAmbHQ7IDEwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVkNjA0XHVjMjE4XHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWMyZGNcdWQwYTRcdWJhNzRcdWMxMWMgXHViNTQ1XHVjNzQ0IFx1YmU0Y1x1YjgyNFx1YzhmY1x1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVhYzAwXHViMmE1XHVkNTVjIFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPigwLDApLSgxLDEpLCAoMiwyKS0oMiwyKTxcL2xpPlxyXG5cdDxsaT4oMSwwKS0oMSwwKSwgKDAsMSktKDAsMSk8XC9saT5cclxuXHQ8bGk+KDIsMCktKDIsMCksICgxLDEpLSgxLDEpPFwvbGk+XHJcblx0PGxpPigxLDEpLSgxLDEpLCAoMCwyKS0oMCwyKTxcL2xpPlxyXG5cdDxsaT4oMiwxKS0oMiwxKSwgKDEsMiktKDEsMik8XC9saT5cclxuXHQ8bGk+KDIsMCktKDIsMSksICgwLDIpLSgxLDIpPFwvbGk+XHJcblx0PGxpPigxLDApLSgyLDApLCAoMCwxKS0oMCwyKTxcL2xpPlxyXG48XC91bD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMTg0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUkFUQVIiLCJkZXNjcmlwdGlvbiI6IjxwPkFmdGVyIE1pcmtvJiMzOTtzIGZhaWxlZCBzdGludCBhcyBhIGNvYWNoIGFuZCBhIHBhc3Npbmcgb2JzZXNzaW9uIHdpdGggQ3JvYXRpYW4gbWVhdCBkZWxpY2FjaWVzLCBoaXMgd2VpZ2h0IHByb2JsZW1zIGhhdmUgbW90aXZhdGVkIGhpbSB0byB3b3JrIGhhcmQgYXMgYSBmYXJtZXIuIEhlIGhhcyBtb3ZlZCB0byBhIHZpbGxhZ2Ugd2hlcmUgaGlzIGZyaWVuZCBTbGF2a28gbGl2ZXMuIEZhcm1lcnMgaW4gdGhlIHZpbGxhZ2Ugc2hhcmUgYSBsYXJnZSBjb21tb24gcGxvdCBvZiBsYW5kIGluIHRoZSBzaGFwZSBvZiBhIE4mdGltZXM7TiBzcXVhcmUsIGRpdmlkZWQgaW50byBOJnN1cDI7IHVuaXQgc3F1YXJlcy4gQSB1bml0IHNxdWFyZSBhdCBjb29yZGluYXRlcyAoaSwgaikgYnJpbmdzIGluIHRoZSBpbmNvbWUgb2YgQTxzdWI+aWo8XC9zdWI+LCB3aGljaCBjYW4gYmUgbmVnYXRpdmUgKGZvciBleGFtcGxlLCBpZiB0aGUgc3F1YXJlIGhhcyB0byBiZSBtYWludGFpbmVkIGJ1dCBpcyBub3QgY3VsdGl2YXRlZCkuIFRoZSBmYXJtZXJzIGFsd2F5cyBkaXZpZGUgdGhlIGNvbW1vbiBsYW5kIGludG8gc21hbGxlciByZWN0YW5ndWxhciBmaWVsZHMgd2l0aCBlZGdlcyBwYXJhbGxlbCB0byB0aGUgY29tbW9uIGxhbmQgZWRnZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlNsYXZrbyBpcyBza2VwdGljYWwgb2YgTWlya28gc2luY2UgaGlzIGZhaWx1cmUgYXMgYSBjb2FjaCwgc28gaGUgaW5zaXN0cyB0aGF0IGJvdGggb2YgdGhlbSBhcmUgYXNzaWduZWQgbGFuZCB3aXRoIHRoZSBzYW1lIHRvdGFsIGluY29tZSwgYnV0IGFsc28gdGhldCB0aGUgdHdvIHBsb3RzIHNoYXJlIGV4YWN0bHkgb25lIGNvbW1vbiBjb3JuZXIgc28gdGhhdCB0aGUgdHdvIGZyaWVuZHMgY2FuIGtlZXAgYW4gZXllIG9uIGVhY2ggb3RoZXIgKFNsYXZrbyBrbm93cyB0aGF0IE1pcmtvIGlzIHByb25lIHRvIG1pc2NoaWVmKS4gVGhlY29tbW9uIGNvcm5lciBtdXN0IGJlIHRoZSBvbmx5IHBvaW50IHdoZXJlIHRoZSB0d28gcGxvdHMgbWVldCwgaW4gb3JkZXIgdG8gcHJldmVudCBib3JkZXItcmVsYXRlZCBhcmd1bWVudHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPllvdSBhcmUgZ2l2ZW4gYSBkZXNjcmlwdGlvbiBvZiB0aGUgY29tbW9uIGxhbmQgcGxvdC4gRmluZCB0aGUgdG90YWwgbnVtYmVyIG9mIHBsb3QgcGFpcnMgdGhhdCBzYXRpc2Z5IFNsYXZrbyYjMzk7cyBjcml0ZXJpYS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBwb3NpdGl2ZSBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgNTApLCB0aGUgZGltZW5zaW9ucyBvZiB0aGUgY29tbW9uIGxhbmQgcGxvdC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgTiBzcGFjZS1zZXBhcmF0ZWQgbnVtYmVycyBBPHN1Yj5pajxcL3N1Yj4gKC0xMDAwICZsdDsgQTxzdWI+aWo8XC9zdWI+ICZsdDsgMTAwMCksIHRoZSBpbmNvbWUgcHJvdmlkZWQgYnkgdGhlIHJlc3BlY3RpdmUgY2VsbC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSB0b3RsIG51bWJlciBvZiBwbG90IHBhaXJzIHNhdGlzZnlpbmcgdGhlIGdpdmVuIGNvbmRpdGlvbi48XC9wPlxyXG4iLCJoaW50IjoiPHA+VGhlIHBvc3NpYmxlIHJlY3RhbmdsZSBwYWlycyBhcmU6ICgwLDApLSgxLDEpIGFuZCAoMiwyKS0oMiwyKSwgKDEsMCktKDEsMCkgYW5kICgwLDEpLSgwLDEpLCAoMiwwKS0oMiwwKSBhbmQgKDEsMSktKDEsMSksICgxLDEpLSgxLDEpIGFuZCAoMCwyKS0oMCwyKSwgKDIsMSktKDIsMSkgYW5kICgxLDIpLSgxLDIpLCAoMiwwKS0oMiwxKSBhbmQgKDAsMiktKDEsMiksICgxLDApLSgyLDApIGFuZCAoMCwxKS0oMCwyKS4mbmJzcDs8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==