Kevin's Home

Description

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

兄弟两回到草原，将可以养马的区域，分为N*N的单位面积的正方形，并实地进行考察，归纳出了每个单位面积可以养马所获得的收益。接下来就要开始规划他们各自的马场了。

首先，两人的马场都必须是矩形区域。同时，为了方便两人互相照应，也为了防止马匹互相走散，规定两个马场的矩形区域相邻，且只有一个交点。最后，互不认输的两人希望两个马场的收益相当，这样才不会影响他们兄弟的感情。

现在，兄弟两找到你这位设计师，希望你给他们设计马场，问共有多少种设计方案。

Input

第一行一个整数N，表示整个草原的大小为N*N。

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

Output

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

Sample Input

3 1 2 3 4 5 6 7 8 9

Sample Output

2

Hint

Source

2014宁波初中 T2

宁波镇海中学的罗方炜给我们组的一场比赛。

此题主要靠技巧。枚举中心点，然后用数组hash。注意数组清空复杂度很大，每次清空必定超时。应该用一个栈来记录更改的地方，直接赋0.