Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

— Cuál es el numero que más te gusta? — pregunta Fito.
— Definitivamente, $2068965517241379310344827586$. — responde Pepe.
— Por qué?
— Primero que todo, su último dígito es $6$, y si lo quitamos de su posición y lo ponemos al comienzo del número entonces su valor es $3$ veces mayor que el original! El otro día mi tarea de matemáticas fue encontrar el $k$-ésimo número con esta propiedad.
— Pero ese número puede ser realmente grande!
— Si, pero para hacerlo simple, el profesor solo nos pidió el resto que dejaba el número módulo $10^9 + 7$. Muy fácil, verdad?

Despues de pensarlo por un rato, Fito se dió por vencido. Por lo que necesita tu ayuda para resolver el problema.

Input

Un número entero $k$ $(1 \leq k \leq 10^9)$ — el número dado por el profesor.

Output

Una línea con la respuesta a la tarea del profesor.

Sample test(s)

Hints

$10^9 + 7$ es primo.