Silent Hill es un juego conocido por, además de su gran y oscura historia, sus complicados y bizarros acertijos. Nyar está en Silent Hill y se estancá en una parte del juego. Está en un hospital mental abandonado y no puede salir. Al recorrer el hospital, encontró 3 pistas que piensa lo ayudaran a descifrar la clave para abrir una caja fuerte en la que está la llave para salir. Esta es la descripción de las 3 pistas.

- Pintura de una mujer sosteniendo lo que parece un corazón en la mano. A su lado un niño abrazando a la mujer con un agujero en el pecho. Esto está justo arriba de la caja fuerte.

- Periódico con encabezado: ”Mujer enloquece y asesina a su único hijo”. Escrito en los bordes del periodico se ve un número X muy grande de muchos dígitos. -

- Poema escrito en el revés de la fotografía de una familia en la playa que dice lo siguiente: ”En sangre quedan plasmados sus infantiles sueños. Y todo en una vez, todas las maneras en las que pudieron partir su corazón.”
Nyar se pone a pensar... cree que el número y el poema que encontró tienen algo que ver con la clave de la caja fuerte. Piensa que el gran número X en el periódico representa al corazón del niño y lo que se debe encontrar es la suma de todos los divisores de  X.

La entrada consta de T casos de prueba, que a lo m ́as ser ́an 100. En cada caso se dan dos números enteros u (1 < u ≤ 1000000) y k (0 < k ≤ 1000000) que representan al número X = u^k.

Imprimir la suma de todos los divisores de X. Como el resultado puede ser muy grande imprimirlo módulo 100000007.