Robert está fascinado con los números y sus propiedades. Recientemente descubrió la función divisor ~d(x)~, que cuenta la cantidad de divisores positivos de un número entero ~x~.

Recordando sus clases de matemáticas, sabe que si la factorización prima de x es: $$\displaystyle x = p_1^{e_1} \times p_2^{e_2} \times \ldots \times p_k^{e_k}$$

Entonces el número de divisores se calcula como: $$\displaystyle d(x) = (e_1 + 1) \times (e_2 + 1) \times \ldots \times (e_k + 1)$$

Por ejemplo: $$\displaystyle d(6) = d(2^1 \times 3^1) = 2 \times 2 = 4$$ $$\displaystyle d(12) = d(2^2 \times 3^1) = 3 \times 2 = 6$$

Ahora Robert define una nueva función ~g(x)~ como el cuadrado del número de divisores: $$\displaystyle g(x) = d(x)^2$$

Y quiere calcular la suma de todos los ~g(x)~ desde ~1~ hasta ~N~: $$\displaystyle G(N) = \sum_{i=1}^{N} g(i) = \sum_{i=1}^{N} d(i)^2$$

Como los números pueden ser enormes, Robert solo necesita el resultado módulo ~10^9 + 7~. Dado un entero ~N~, calcule ~G(N)~ módulo ~10^9 + 7~.

Entrada

Un único entero ~N~.

Salida

Un único entero que representa ~G(N)~ módulo ~10^9 + 7~.

Restricciones

• ~1 \leq N \leq 10^{11}~

Subtareas

Subtarea	Puntos	Restricción
1	2	~N \leq 10^2~
2	8	~N \leq 10^3~
3	10	~N \leq 10^5~
4	20	~N \leq 10^7~
5	30	~N \leq 10^9~
6	30	Sin restricciones adicionales

Ejemplos de Entrada y Salida

Ejemplo #1 de Entrada

6

Ejemplo #1 de Salida

38

Explicación

i	Factorización	~d(i)^2~
1	~1~	~1~
2	~2^1~	~4~
3	~3^1~	~4~
4	~2^2~	~9~
5	~5^1~	~4~
6	~2^1 \times 3^1~	~16~

~G(6) = 1 + 4 + 4 + 9 + 4 + 16 = 38~

Ejemplo #2 de Entrada

100

Ejemplo #2 de Salida

3046