1102. Number of Increasing Paths in Grid

Given an m x n grid of integers, count the number of strictly increasing paths (moving 4-directionally, each next cell strictly greater), where paths of length 1 (a single cell) also count. Return the total modulo 1000000007. The input is JSON {grid}.

Input: JSON {grid}.

Output: Integer — the count of increasing paths, modulo 1e9+7.

Examples

Input: {"grid":[[1,1],[3,4]]}
Output: 8
Explanation: Four single cells plus four longer paths.

Input: {"grid":[[1]]}
Output: 1
Explanation: Just the single cell.

Input: {"grid":[[1,2,3],[4,5,6],[7,8,9]]}
Output: 53
Explanation: All strictly increasing paths, single cells included.

Constraints

• 1<=rows,cols<=1000

Asked by