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

"""
DFS at each point.
How do we count?

DFS with DP

If we start at the first one, then there's

Length of 3 means.

1 + 1 + 1
2 + 2
3

6 paths
3 + 2 + 1
length + 1
(N*(N+1)) // 2

At each point track length.
If you reach a point that has it set, then use the set value.
At each point it should be the number of increasing paths. This can be multiple.
Max length of each increasing path (max of 4).

How to make sure we don't double count?
* Track it from each point.
Sum instead of using the summation formula.
"""


class Solution:
    def dfs(self, row, col, dp, grid):
        if dp[row][col] is not None:
            return dp[row][col] + 1

        dp[row][col] = 0
        curr_sum = 0

        if row - 1 >= 0 and grid[row - 1][col] > grid[row][col]:
            curr_sum += self.dfs(row - 1, col, dp, grid)

        if row + 1 < len(dp) and grid[row + 1][col] > grid[row][col]:
            curr_sum += self.dfs(row + 1, col, dp, grid)

        if col - 1 >= 0 and grid[row][col - 1] > grid[row][col]:
            curr_sum += self.dfs(row, col - 1, dp, grid)

        if col + 1 < len(dp[0]) and grid[row][col + 1] > grid[row][col]:
            curr_sum += self.dfs(row, col + 1, dp, grid)
        dp[row][col] = curr_sum

        return curr_sum + 1

    def countPaths(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        dp = [[None] * cols for _ in range(rows)]
        res = 0

        for r in range(rows):
            for c in range(cols):
                res += self.dfs(r, c, dp, grid)

        return res % (10**9 + 7)

1127