Robot Grid Paths

Given an N × M grid, a robot starts at the top-left cell and needs to reach the bottom-right cell. The robot can only move in one of three directions: right, down, or diagonally down-right. Your task is to count the number of distinct paths the robot can take to reach the destination.

The recurrence relation used to compute the number of paths is given by:

[ \text{dp}{i,j} = \left(\text{dp}{i-1,j} + \text{dp}{i,j-1} + \text{dp}{i-1,j-1}\right) \mod 10^9+7, ]

with the initial condition \(\text{dp}_{1,1} = 1\). Here, \(\text{dp}_{i,j}\) represents the number of ways to reach cell \((i, j)\) in a grid with 1-indexed rows and columns.

You need to handle multiple test cases.

inputFormat

The first line of input contains a single integer \(T\) denoting the number of test cases. Each of the following \(T\) lines contains two space-separated integers \(N\) and \(M\), the number of rows and columns of the grid respectively.

outputFormat

For each test case, output a single line containing the number of distinct paths from the top-left to the bottom-right cell modulo \(10^9 + 7\).

## sample

1
1 1

1

</p>