Dado un número entero, tu tarea consiste en hallar el número, la suma y el producto de sus divisores. Como ejemplo, consideremos el número ~12~:

• el número de divisores es ~6~ (son ~1, 2, 3, 4, 6, 12~).
• la suma de los divisores es ~1+2+3+4+6+12=28~.
• el producto de los divisores es ~1 \cdot 2 \cdot 3 \cdot 4 \cdot 6 \cdot 12 = 1728~.

Dado que el número de entrada puede ser grande, se da como una factorización de primos.

Entrada

La primera línea tiene un número entero ~n~: el número de partes de la factorización primaria. Después de esto, hay ~n~ líneas que describen la factorización. Cada línea tiene dos números ~x~ y ~k~ donde ~x~ es un primo y ~k~ es su potencia.

Salida

Imprime tres enteros módulo ~10^9+7~: el número, la suma y el producto de los divisores.

Restricciones

• ~1 \leq n \leq 10^5~
• ~2 \leq x \leq 10^6~
• cada ~x~ es un primo distinto
• ~1 \leq k \leq 10^9~

Ejemplo de Entrada

2
2 2
3 1

Ejemplo de Salida

6 28 1728