You are given an n×n grid where each square contains an integer between 1…n^2.

A route in the grid starts from some square and moves always either vertically or horizontally into another square, which has a smaller number than the current square. The squares need not be adjacent, and a route can consist of only a single square (meaning every number themselves is a path already).

How many different routes are there in the grid? Because the answer may be large, print it modulo 10^9 7, i.e. the remainder when dividing the answer by 10^9 7.

Input

The first line contains an integer n: the size of the grid.

The following n lines each contain n integers: the contents of the grid.

Output

Print one integer: the number of routes modulo 10^9 7.

Example

Input: 3

2 1 3

1 1 1

9 2 7

Output: 46 Explanation: In this example, the following three are possible routes among others:

Time complexity for this should be max. O(n^2). But I am sure there is a solution for O(n) or O(n log n).

How should I edit my code to calculate every path, including for example those that go vertically first and then horizontally and still continue their way somewhere.

So far, my code only calculates paths directly from each number to smaller one(s) vertically and horizontally.

`

#include <bits/stdc  .h>

using namespace std;

int main() {
    int n, k = 0, l = 0, row, column, paths = 0;
    cin>>n;
    int grid[n][n];
    for (row = 0; row < n; row  ) {
        for (column = 0; column < n; column  ) {
            cin>>grid[row][column];
        }
    }
    for (row = 0; row < n; row  ) {
        for (column = 0; column < n; column  ) {
            k = 0;
            l = 0;
            for (k = 0; k < n; k  ) {
                if(grid[row][column]>grid[row][0 k] && grid[row][0 k] != 0) {
                    paths  ;
                }
            }
            for (l = 0; l < n; l  ) {
                if(grid[row][column]>grid[0 l][column] && grid[0 l][column] != 0) {
                    paths  ;
                }
            }
        }
    }
        cout<<paths;
}

`

CodePudding user response：

This problem describes a directed graph: every square has a number of (directed) neighbours that are in a horizontal or vertical direction with a smaller number than the start square. The number asked for then devolves to finding all possible paths in this graph.

A solution sketch:

1. Create a vertex for every item in the grid. Its value is the value in the grid.
2. For every vertex, add neighbours that are in the same row or column with a smaller number.
3. For every vertex, count the number of paths that are reachable, including the "single-tile" path.

Now, to make this efficient, you can use dynamic programming to remember the number of paths starting from a given vertex. Furthermore, you can walk the vertexes in increasing number order to make sure all down stream paths have already been computed.

This algorithm is O(n) in the number of grid cells.