Concurso de Sumas


Submit solution

Points: 100
Time limit: 1.0s
Memory limit: 260M

Authors:
Problem types
Allowed languages
C++, Python, Rust

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


Comments

There are no comments at the moment.