Descripción

Karel tiene muchos amigos con los que se lleva bien. Desgraciadamente, no todos los amigos de Karel se llevan bien entre ellos (no cumplen la propiedad transitiva de la igualdad). Resulta que Karel está por cumplir 45 años desde su creación, es por eso que decidió celebrarlo y hacer una fiesta con todos sus \(N-1\) amigos. Resulta que los amigos de Karel son en general muy egocéntricos, y si uno se parece mucho a otro, significa que estos no se llevarán bien. Los \(N-1\) amigos, y Karel, se sentarán en una mesa rectangular, de un solo lado (como en la última cena). Cada amigo está numerado del \(2\) al \(N\). Karel quiere evitar las peleas entre amigos durante la cena, por lo que no pondrá amigos que se parecen mucho juntos.

\(2\) amigos se parecen si la diferencia absoluta de sus números es \(1\). Ej. el amigo \(4\) no se llevará bien ni con el \(5\), ni con el \(3\).

Karel se la pasó increíble en su fiesta, y justo cuando estaba a punto de dormir, empezó a tener pensamientos intrusivos, sobre lo que hubiera ocurrido si es que 2 amigos parecidos se sentaban juntos... Así que para poder dormir, decidió pensar en otra cosa, de cuántas formas distintas pudo haber sentado a sus \(N\) invitados (él incluido) en la mesa sin que hubiera amigos parecidos sentados juntos. Dos acomodos se consideran distintos si en al menos una posición de la mesa se sienta una persona diferente, es decir, el orden sí importa.

Como el número de acomodos puede ser gigantesco, Karel solo quiere saber el resultado módulo \(10^9+7\).

Entrada

Un entero positivo \(N\) que indicará la gente que asistirá a la fiesta de Karel (Karel está incluido en \(N\), y siempre será representado por \(1\)).

Salida

Imprime un solo entero: la cantidad de acomodos distintos, módulo \(10^9+7\), en los que se puede sentar a las \(N\) personas de forma que no haya dos amigos parecidos sentados juntos.

Ejemplo 1

Entrada

4

Salida

2

Ejemplo 2

Entrada

10

Salida

479306

Consideraciones

• Si no existe ningún acomodo válido, la respuesta simplemente es \(0\) (no es necesario imprimir "NO SOLUTION").
• El orden de las personas en la mesa importa: dos acomodos que sean reflejo uno del otro (leídos de derecha a izquierda) se cuentan como distintos.
• (Sí, a Karel le sigue cayendo mal su amigo 2).

Límites

• \(2\leq N\leq10^6\)