Dada un número natural $n$, cuente el número de permutaciones $(p_1, p_2, \dots, p_n)$ de los números del 1 al $n$, tales que para cada $i$ ($1 \le i \le n$), se cumpla la siguiente propiedad: $p_i \pmod{p_{i+1}} \le 2$, donde $p_{n+1} = p_1$.

Como este número puede ser muy grande, imprímalo módulo $10^9 + 7$.

Entrada

La única línea de la entrada contiene el entero $n$ ($1 \le n \le 10^6$).

Salida

Imprima un único entero: el número de permutaciones que satisfacen la condición del enunciado, módulo $10^9 + 7$.

Ejemplos

Entrada 1

1

Salida 1

1

Entrada 2

2

Salida 2

2

Entrada 3

3

Salida 3

6

Entrada 4

4

Salida 4

16

Entrada 5

5

Salida 5

40

Entrada 6

1000000

Salida 6

581177467

Nota

Por ejemplo, para $n = 4$ usted debe contar la permutación $[4, 2, 3, 1]$, ya que $4 \pmod 2 = 0 \le 2$, $2 \pmod 3 = 2 \le 2$, $3 \pmod 1 = 0 \le 2$, $1 \pmod 4 = 1 \le 2$. Sin embargo, no debe contar la permutación $[3, 4, 1, 2]$, ya que $3 \pmod 4 = 3 > 2$, lo cual viola la condición del enunciado.