Concurso de Sumas
Problema
Calcule la suma de todas las posibles sumas de sumandos extraidos del conjunto
Por ejemplo, para el conjunto se pueden extraer las siguentes sumas de sumandos:
Como el resultado puede ser grande, solo se necesita su valor módulo .
Tarea
Para cada caso de prueba, calcule la suma de todas las posibles sumas de elementos del conjunto .
Entrada
La primera línea de la entrada contiene un entero , el número de casos de prueba, a partir de ahí, líneas, cada una con dos enteros y .
Salida
Imprimir líneas, cada una con la respuesta a su respectivo caso de prueba módulo .
Límites
Subtareas
- (5 puntos) y
- (20 puntos) y
- (25 puntos) y
- (50 puntos)
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 , de ahí solamente se pueden formar las sumas de 1 () elemento siguientes:
Para el segundo caso de prueba, el conjunto es: , y se pueden formar las siguientes sumas de dos () elementos:
Comments