Sekai ha pensado en abrir una tienda de componentes electrónicos, y como toda buena tienda necesita una caja registradora. Él quiere comenzar a generar los códigos de barra para sus productos pero no sabe que ancho deben tener estos y si habrán suficientes códigos válidos para todos sus productos, ya que todos deben ser distintos. Por eso Sekai se formuló el siguiente problema:

Dado ~M~ cuántos códigos de barra válidos de ancho ~M~ existen.

Un código de barra es una serie de barras negras o blancas adyacentes de ancho 1 o 2, de tal manera que los anchos de todas suman ~M~.

Para más claridad, los siguientes son ejemplos de códigos de barra (cada barra aparece con su respectivo ancho en la parte inferior).

Se dice que un código de barra es válido cuando comienza con una barra negra y termina con una barra negra, y no existen dos barras consecutivas del mismo color. Note que las barras pueden tener ancho 1 o 2 sin necesidad de repetirse.

Los siguientes son ejemplos de códigos de barra válidos e inválidos.

• El código de la izquierda es válido (comienza y termina en barras negras y no hay dos barras adyacentes del mismo color).
• El código del medio no es válido (hay barras adyacentes del mismo color y termina en una barra blanca en vez de una negra).
• El código de la derecha no es válido (comienza con una barra blanca en vez de una negra).

Entrada

La primera y única línea contiene el entero ~1\leq M\leq10^{5}~, el ancho del código de barra.

Salida

Imprima una sola línea, la cantidad de códigos válidos ~\mod 10^{9}+7~.

Subtareas

Subtareas:

• Subtarea 1: ~M\leq5~ (5 puntos).
• Subtarea 2: ~M\leq16~ (15 puntos).
• Subtarea 3: ~M\leq10^{3}~ (20 puntos)
• Subtarea 4: Sin restricciones adicionales (60 puntos)

Ejemplos

Entrada 1

6

Salida 1

6

Entrada 2

12

Salida 2

116