<p>You are given an <code>m x n</code> integer matrix <code>grid</code>, where you can move from a cell to any adjacent cell in all <code>4</code> directions.</p>

<p>Return <em>the number of <strong>strictly</strong> <strong>increasing</strong> paths in the grid such that you can start from <strong>any</strong> cell and end at <strong>any</strong> cell. </em>Since the answer may be very large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>Two paths are considered different if they do not have exactly the same sequence of visited cells.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/05/10/griddrawio-4.png" style="width: 181px; height: 121px;" />
<pre>
<strong>Input:</strong> grid = [[1,1],[3,4]]
<strong>Output:</strong> 8
<strong>Explanation:</strong> The strictly increasing paths are:
- Paths with length 1: [1], [1], [3], [4].
- Paths with length 2: [1 -&gt; 3], [1 -&gt; 4], [3 -&gt; 4].
- Paths with length 3: [1 -&gt; 3 -&gt; 4].
The total number of paths is 4 + 3 + 1 = 8.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1],[2]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> The strictly increasing paths are:
- Paths with length 1: [1], [2].
- Paths with length 2: [1 -&gt; 2].
The total number of paths is 2 + 1 = 3.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 1000</code></li>
	<li><code>1 &lt;= m * n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= grid[i][j] &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution:
    def countPaths(self, grid: List[List[int]]) -> int:
        """
        Probably want to start by converting to a DAG, or at least
        conceptualizing it as such.

        Then you can... break it apart? Maybe something to do with connected
        components? Outside chance that it could be a flow/max cut problem?

        It seems there is a known DP for finding/counting paths between two
        vertices in a DAG. If there are n vertices, you could naively track
        a nxn table where element i,j counts the paths between vertices i and
        j. Then you could just use a priority queue and work your way outwards
        from each node. Of course, we have up to 1e6 nodes, so that might be...
        bad. Maybe we can optimize by utilizing the ordering of nodes?

        Yes, if you fully solve all larger nodes first, then you know that the
        answer for a smaller node is just the sum of the totals for all
        adjacent larger nodes (plus one for the trivial self path).

        Obviously a locally maximal node will only have 1 path.
        """
        def bigger_neighbors(i, j):
            # Get neighbors with larger values
            bn_indices = []
            # Larger row index possible
            if i < len(grid) - 1:
                if grid[i][j] < grid[i + 1][j]:
                    bn_indices.append((i + 1, j))
            # Smaller row index possible
            if i > 0:
                if grid[i][j] < grid[i - 1][j]:
                    bn_indices.append((i - 1, j))
            # Larger col index possible
            if j < len(grid[i]) - 1:
                if grid[i][j] < grid[i][j + 1]:
                    bn_indices.append((i, j + 1))
            # Smaller col index possible
            if j > 0:
                if grid[i][j] < grid[i][j - 1]:
                    bn_indices.append((i, j - 1))
            return bn_indices

        # Count paths rooted at each cell
        n_paths_from = [[None for _ in row] for row in grid]
        queue = deque()
        for next_i in range(len(grid)):
            for next_j in range(len(grid[next_i])):
                # Prepare to solve
                queue.append((next_i, next_j))
                while queue:
                    i, j = queue[0] # Peek until we know it can be solved now
                    # Catch already solved node
                    if n_paths_from[i][j] is not None:
                        queue.popleft()
                        continue
                    # Ensure that larger neighbors are solved first
                    bn_lst = bigger_neighbors(i, j)
                    all_bn_solved = True
                    possible_solution = 1
                    for bi, bj in bn_lst:
                        if n_paths_from[bi][bj] is None:
                            queue.appendleft((bi, bj))
                            all_bn_solved = False
                        else:
                            possible_solution += n_paths_from[bi][bj]
                    if all_bn_solved:
                        # Solve node
                        n_paths_from[i][j] = possible_solution
                        queue.popleft()

        ans = 0
        for row in n_paths_from:
            for n in row:
                ans = (ans + n) % int(1e9 + 7)
        return ans
70134