Equal Profit Horse Farms

Two brothers from the grasslands, inspired by a war horse review, have decided to become superb "horse farmers" by raising war horses. They have divided a region into an N × N grid of unit square cells. Each cell has an associated profit value if horses are raised there. Now, each brother will choose a rectangular area as his horse farm. The following restrictions apply:

• Both farms must be rectangular regions (submatrices aligned with the grid).
• The two rectangular farms must be adjacent in such a way that they share exactly one common point (i.e. one common corner) and no common edge.
• The profit obtained from each chosen farm (i.e. the sum of profits of its cells) must be equal.

The adjacency condition forces the two rectangles into one of two possible configurations. Assume the grid cells are indexed from 1 to N in both rows and columns. Then there exists a grid intersection point (pivot) with coordinates \((i,j)\) (with \(1 \le i,j \le N-1\)). The two possible configurations are as follows:

Configuration 1 (Top‐Left & Bottom‐Right):

• The first rectangle has its bottom‐right corner fixed at \((i,j)\). Thus it can be any submatrix ending at \((i,j)\): defined by choosing its top row \(r\) and left column \(c\) with \(1 \le r \le i\) and \(1 \le c \le j\).
• The second rectangle has its top‐left corner fixed at \((i+1,j+1)\). It is defined by choosing its bottom row \(r'\) and right column \(c'\) with \(i+1 \le r' \le N\) and \(j+1 \le c' \le N\).

Configuration 2 (Top‐Right & Bottom‐Left):

• The first rectangle has its bottom‐left corner fixed at \((i, j+1)\). It can be chosen by fixing the bottom row as \(i\) and then choosing a top row (from 1 to \(i\)) and a right column (from \(j+1\) to \(N\)).
• The second rectangle has its top‐right corner fixed at \((i+1, j)\). It can be chosen by fixing the top row as \(i+1\) and then choosing a bottom row (from \(i+1\) to \(N\)) and a left column (from 1 to \(j\)).

Your task is to count the number of design schemes (i.e. pairs of rectangles from either configuration) that satisfy the profit equality condition.

Input Format: The first line contains an integer \(N\)\, denoting the size of the grid. The following \(N\) lines each contain \(N\) integers representing the profit values for the cells.

Output Format: Output a single integer, the total number of valid design schemes.

Note: Use prefix sums to compute submatrix sums efficiently. All formulas are given in \(\LaTeX\) format.

inputFormat

The first line contains an integer \(N\)\, (\(N \ge 2\)). Each of the next \(N\) lines contains \(N\) space-separated integers representing the profit values of the grid cells.

outputFormat

Print a single integer: the number of valid design schemes.

sample

2
1 2
3 4

0