A diferencia de La Paz y Santa Cruz de la Sierra, se dice que El Alto es una ciudad cuadriculada, porque muchas calles se parecen y su distribución se observa como una cuadrícula.

Representamos esta ciudad mediante una cuadrícula de n filas y m columnas. Empiezas en la celda de la esquina superior izquierda y deseas llegar a la esquina inferior derecha.

En cada movimiento puedes avanzar una cantidad positiva arbitraria de celdas en una de estas dos direcciones:

• Hacia abajo.
• Hacia la derecha.

Calcula el número de secuencias de movimientos diferentes que permiten llegar al destino, módulo 109 + 7.

La primera línea contiene el entero t (1 ≤ t ≤ 100). Cada caso consiste en dos enteros n y m (1 < n, m ≤ 1500), las dimensiones de la cuadrícula.

Por cada caso imprime el número de recorridos distintos módulo 109 + 7.