Un texto de dígitos es bueno si en las posiciones pares (contando desde \(0\)) tiene dígitos pares y en las impares tiene dígitos primos (\(2\), \(3\), \(5\) o \(7\)). Por ejemplo, 2582 es bueno y 3245 no. Se permiten ceros a la izquierda. Cuenta los textos buenos de largo \(n\).

Entrada

Un entero \(n\) \((1 \le n \le 10^{15})\).

Salida

La cantidad, módulo \(10^9 + 7\).

Ejemplo 1

Entrada

1

Salida

5

Ejemplo 2

Entrada

4

Salida

400

Ejemplo 3

Entrada

50

Salida

564908303