<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:
        '''
        let's do dp bottom-up
        the max cells only have 1 path that start from them.
        we will do bfs from each max cell, and evaluate neighbors that are strictly lower, by 
        '''
        N,M=len(grid),len(grid[0])
        dp=[[1]*M for _ in range(N)]
        pq=[]
        for n in range(N):
            for m in range(M):
                heapq.heappush(pq,(-grid[n][m],n,m))
        while pq:
            (_,n,m)=heapq.heappop(pq)
            
            B=[(n-1,m),(n,m-1),(n+1,m),(n,m+1)]
            for (y,x) in B:
                if 0<=y<N and 0<=x<M and grid[y][x]<grid[n][m]:
                    dp[y][x]+=dp[n][m]
        
        result=0
        for n in dp:
            result+=sum(n)
        return result%((10**9)+7)

    def dp_mle_countPaths(self, grid: List[List[int]]) -> int:
        N,M=len(grid),len(grid[0])
        dp=[[1]*M for _ in range(N)]
        pairs=deque()

        for n in range(N):
            for m in range(M):
                B=[(n-1,m),(n,m-1),(n+1,m),(n,m+1)]
                for (y,x) in B:
                    if 0<=y<N and 0<=x<M and grid[y][x]>grid[n][m]:
                        dp[y][x]+=1
                        pairs.append((y,x))                        
        
        while pairs:
            (n,m)=pairs.popleft()
            B=[(n-1,m),(n,m-1),(n+1,m),(n,m+1)]
            for (y,x) in B:
                if 0<=y<N and 0<=x<M and grid[y][x]>grid[n][m]:
                    dp[y][x]+=1
                    pairs.append((y,x))                        
        
        result=0
        for n in dp:
            result+=sum(n)
        return result

    def mle_countPaths(self, grid: List[List[int]]) -> int:
        '''
        this looks like combinatorics question.
        for any given input, we start with N*M paths of length=1
        for paths of length=2 we need to consider the movement.
        we need to traverse grid and add all pairs (a,b) where a!=b and a<b.
        then, for each pair (a,b) we can add all the pairs (b,c)
        then, for each triplet (a,b,c) we can add all the pairs (c,d)
        etc.

        at each iteration, we only need to keep the cell we ended with.
        '''
        N,M=len(grid),len(grid[0])

        pairs=deque()
        for n in range(N):
            for m in range(M):
                pairs.append((n,m,1))
        
        # 4
        result = len(pairs)
        mem=defaultdict(lambda: 1)

        while pairs:
            #0,0,1 0,1,1 1,0,1 1,0,2 1,1,2 1,1,2 1,1,3
            (n,m,l)=pairs.popleft()
            B=[(n-1,m),(n,m-1),(n+1,m),(n,m+1)]
            for (y,x) in B:
                if 0<=y<N and 0<=x<M and grid[y][x]>grid[n][m]:
                    #1,0,2 1,1,2 1,1,2 1,1,3
                    b=(y,x,l+1)
                    if b in mem:
                        mem[b]+=1
                    else:
                        pairs.append(b)
                        mem[b]=1
                    result+=mem[(n,m)]
        
        return result%((10**9)+7)

2146