Problema

Calcule la suma de todas las posibles sumas de ~K~ sumandos extraidos del conjunto ~\{1,2,3,...,N\}~

Por ejemplo, para el conjunto ~\{1,2,3\}~ se pueden extraer las siguentes sumas de ~2~ sumandos: ~(1+2) + (1+3) + (2+3)=12~

Como el resultado puede ser grande, solo se necesita su valor módulo ~10^9+7~.

Tarea

Para cada caso de prueba, calcule la suma de todas las posibles sumas de ~K~ elementos del conjunto ~S_k~.

Entrada

La primera línea de la entrada contiene un entero ~T~, el número de casos de prueba, a partir de ahí, ~T~ líneas, cada una con dos enteros ~N~ y ~K~.

Salida

Imprimir ~T~ líneas, cada una con la respuesta a su respectivo caso de prueba módulo ~10^9+7~.

Límites

• ~1 \le T \le 20~
• ~1 \le K \le N \le 10^6~

Subtareas

• (5 puntos) ~K=1~ y ~1\le N\le 50~
• (20 puntos) ~K\in[1;2]~ y ~1\le N\le 10^6~
• (25 puntos) ~K\in[4;7]~ y ~4\le N\le 10~
• (50 puntos) ~1 \le K \le N \le 10^6~

Ejemplo de entrada

2
2 1
3 2

Ejemplo de salida

3
12

Explicación del ejemplo

Para el primero caso de prueba, tenemos el conjunto ~S_2 = \{1,2\}~, de ahí solamente se pueden formar las sumas de 1 (~k=1~) elemento siguientes: ~(1) + (2) = 3~

Para el segundo caso de prueba, el conjunto es: ~S_3 = \{1,2,3\}~, y se pueden formar las siguientes sumas de dos (~k=2~) elementos: ~(1+2)+(1+3)+(2+3)=12~