Company: infosys_11oct
Difficulty: medium
Funny Jumping Game Problem Description There is a grid (N rows and M columns) of integers. You want to create a funny jumping game. In this game, you start from any cell (r, c), and you have two options for movement: Move to a cell (newr, c) where r < newr, if and only if grid[r][c] >= grid[newr][c]. Move to a cell (r, newc) where c < newc, if and only if grid[r][c] <= grid[r][newc]. If you cannot make any move, the game ends. Define a "PATH" as all the cells (r, c) you visited, maintaining the order of visits. Define "A" as the maximum number of cells that the "PATH" can reach. Define "B" as the number of distinct "PATH"s of length "A" modulo 10 9 + 7. We say that two paths, path1 and path2, of length "A" are different if there exists at least one position K (where 1 <= K <= "A") such that the cell at position K in path1 is different from the cell at position K in path2. Your task is to find the product of "A" and "B". Input Format: The first line contains an integer