Number of Increasing Paths in a Grid

Challenge Points: 30

Level: Hard

You are given a 2D matrix grid of size m x n, where each cell contains an integer.
You are allowed to move from a cell to any of its 4 adjacent neighbors (up, down, left, right).

You need to count all possible paths such that the values along the path are strictly increasing.
A path may begin from any cell and may end at any cell.

Two paths are considered different if the sequence of visited cells differs in any way.
Since the total number of such paths can be very large, return the answer modulo 1,000,000,007.

Example 1:

Input: grid = [[2, 5], [4, 6]]

Output: 10

Explanation:

Valid increasing paths are: Length 1: [2], [5], [4], [6] → 4 paths Length 2: [2 → 4], [2 → 5], [4 → 6], [5 → 6] → 4 paths Length 3: [2 → 4 → 6], [2 → 5 → 6] → 2 paths Total = 4 + 4 + 2 = 10