Autores: Alejandra Schild, Martín Muñoz

Tiempo límite: 1 segundo

Memoria límite: 256 megabytes

Hace unos años el CERN lanzó el laboratorio de física más grande del universo.

Una tarea muy importante que realizan acá se trata de lanzar neutrinos por un tubo que forma una rueda grande. Normalmente, el neutrino entra al tubo, da una vuelta y llega donde mismo.

Sin embargo, hace poco encontraron un neutrino que es más impredecible y lo bautizaron “Pablo”. Por cuestiones cuánticas que aún están estudiando, este neutrino parece que a veces salta entre secciones del tubo que los demás neutrinos no.

El comportamiento del neutrino en el tubo se puede modelar de la siguiente forma: el tubo está formado por las secciones \(1, 2, \ldots , n\), donde la \(i\) está conectada bidireccionalmente a la \(i+ 1\), cuando \(1 \le i< n\); y la \(n\) está conectada a la \(1\).

El neutrino comienza en la sección 1 y luego puede seguir por la 2 o la \(n\). La regla general del movimiento del neutrino es que si ya ha estado en las secciones \(a, a+ 1, \ldots , n-1, n, 1, 2, \ldots , b-1, b\), la siguiente sección puede ser \(a-1\) o \(b+ 1\).

Aparte de estos movimientos, el neutrino, en vez de moverse, puede entrar a un estado muy extraño que los físicos han modelado como “estar en la sección \(\infty\)”. Básicamente el neutrino desaparece por un momento, y con eso desbloquea’‘ todas las secciones, y puede comenzar a moverse de sección a sección sin importar si está conectada o no.

Por ejemplo, si \(n= 10\), y comienza en las secciones \(1, 2, 10, 9, 3\) luego puede entrar a la sección \(\infty\) y seguir con \(6, 7, 5, 8\). Otra secuencia posible es \(1, 2, 3, \infty , 4, 5, 7, 9, 8, 10, 6\).

El neutrino continúa hasta que haya visto todas las secciones, incluyendo la sección \(\infty\).

Los físicos quieren estudiar todas los movimientos posibles que puede hacer Pablo. El primer paso es contar cuántas secuencias hay. ¿Los ayudas?

Entrada

Un único entero \(n\) (\(3 \le n\le 10^{6}\)).

Salida

Imprime la cantidad de secuencias. El número puede ser muy grande, así que imprímelo módulo \(10^{9} + 7\).

Ejemplos

Entrada 1

3

Salida 1

6

Entrada 2

4

Salida 2

18

Entrada 3

10

Salida 3

473280

Nota

Para \(n= 4\), las secuencias posibles son:

• \(1, 2, 3, 4, \infty\)

• \(1, 2, 3, \infty , 4\)

• \(1, 2, 4, \infty , 3\)

• \(1, 2, \infty , 3, 4\)

• \(1, 2, \infty , 4, 3\)

• \(1, 4, 2, 3, \infty\)

• \(1, 4, 2, \infty , 3\)

• \(1, 4, 3, 2, \infty\)

• \(1, 4, 3, \infty , 2\)

• \(1, 4, \infty , 2, 3\)

• \(1, 4, \infty , 3, 2\)

• \(1, \infty , 2, 3, 4\)

• \(1, \infty , 2, 4, 3\)

• \(1, \infty , 3, 2, 4\)

• \(1, \infty , 3, 4, 2\)

• \(1, \infty , 4, 2, 3\)

• \(1, \infty , 4, 3, 2\)