Count Paths in a Grid with Diagonal Moves

You are given a grid with m rows and n columns. A robot starts at the top-left corner (cell (1,1)) and needs to reach the bottom-right corner (cell (m,n)). The robot is allowed to move in three directions:

• Right: from (i, j) to (i, j+1)
• Down: from (i, j) to (i+1, j)
• Diagonally Down-Right: from (i, j) to (i+1, j+1)

Compute the number of distinct paths the robot can take. Since the answer can be large, output it modulo \(10^9+7\).

Input Format: Two space-separated integers representing m and n.

Output Format: A single integer denoting the number of paths modulo \(10^9+7\).

inputFormat

The input consists of a single line containing two space-separated integers m and n, which denote the number of rows and columns of the grid, respectively.

outputFormat

Output a single integer representing the number of distinct paths from the top-left corner to the bottom-right corner modulo \(10^9+7\).

2 2

3