Su tarea consiste en calcular ~n~ coeficientes binomiales módulo ~10^9+7~. Un coeficiente binomial ~{a \choose b}~ se puede calcular mediante la fórmula ~\frac{a!}{b!(a-b)!}~. Suponemos que ~a~ y ~b~ son enteros y que ~0 \leq b \leq a~.

Entrada

La primera línea de entrada contiene un entero ~n~: el número de cálculos. Después, hay ~n~ líneas, cada una con dos enteros ~a~ y ~b~.

Salida

Imprima cada coeficiente binomial módulo ~10^9+7~.

Restricciones

• ~1 \leq n \leq 10^5~
• ~0 \leq b \leq a \leq 10^6~

Ejemplo de Entrada

3
5 3
8 1
9 5

Ejemplo de Salida

10
8
126