<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>

'''
Return the number of strictly increasing paths in the grid, such that you can start from any cell and end at any cell.
Seems like it's a DFS starting at every cell, but then keeping track of the unique sub-paths. 
Let's say we are iterating through nodes 1 -> 3 -> 4
[1,3,4] [1,3] and [3,4] are unique paths.

Perhaps we can use a backtracking algorithm, keeping track of unique sequences, and store a count of the unique paths encountered.

Approaches:
1) At every cell, we can DFS and compute the number of increasing paths that start at that cell. Then store it in a data-structure. Use computation later (memoization). Then for neighbor cells, we can calculate unique paths via DFS and memoized data and avoid repeated sequences. 

Once we get the number of paths ending at cell grid[i][j] and 
update memo[i][j], it means the cell grid[i][j] is visisted.


TC: O(mn * 4^d) w/o memoization - where m,n is the rows and columns respectively. And d is the longest depth of the recursive call.
SC: O(mn)

W/ memoization
TC: O(mn) w/ memoization 
SC: O(mn) 

'''
class Solution:

    def countPaths(self, grid: List[List[int]]) -> int:
        mod = 10**9+7  # Define the modulus
        dirs = [(0,1),(1,0),(0,-1),(-1,0)]
        rows, cols = len(grid), len(grid[0])
        row = [-1 for _ in range(cols)]
        memo = [row[:] for _ in range(rows)]

        def outofbounds(x, y):
            return (x < 0 or x >= len(grid) 
                    or y < 0 or y >= len(grid[0]))
        
        def dfs(i, j):
            # We have visited this cell before, return computed paths
            if memo[i][j] != -1:
                return memo[i][j]
            cnt = 1
            for dir in dirs:
                x = i + dir[0]
                y = j + dir[1]
                if outofbounds(x,y):
                    continue
                if grid[x][y] > grid[i][j]:
                    cnt = (cnt + dfs(x,y)) % mod
            # Store the computed paths for that cell.
            memo[i][j] = cnt 
            return cnt
        
        # Initial result is 0
        res = 0
        # For each un-visited cell, run a DFS
        for i in range(rows):
            for j in range(cols):
                if memo[i][j] == -1:
                    memo[i][j] = dfs(i, j)
                res = (res + memo[i][j]) % mod
        
        return res
1502