#P2363. 马农

马农

题目描述

在观看完战马检阅之后,来自大草原的两兄弟决心成为超级“马农”,专门饲养战马。

兄弟两回到草原,将可以养马的区域,分为N*N的单位面积的正方形,并实地进行考察,归纳出了每个单位面积可以养马所获得的收益。接下来就要开始规划他们各自的马场了。首先,两人的马场都必须是矩形区域。同时,为了方便两人互相照应,也为了防止马匹互相走散,规定两个马场的矩形区域相邻,且只有一个交点。最后,互不认输的两人希望两个马场的收益相当,这样才不会影响他们兄弟的感情。现在,兄弟两找到你这位设计师,希望你给他们设计马场,问共有多少种设计方案

输入格式

第一行一个整数N,表示整个草原的大小为N*N。接下来N行,每行N个整数A(i,j),表示第i行第j列的单位草地的收成。(注意:收益可能是负数,养马也不是包赚的,马匹也可能出现生病死亡等意外。)

输出格式

输出符合两人要求的草原分配方案数。

3
1 2 3
4 5 6
7 8 9
2

提示

数据范围及约定

对于所有数据,1n501\le n\le 50