Descripción

El Gran Maestro Zurg, un ser de inmensa sabiduría (y un gusto por los dulces excesivamente azucarados), ha decidido celebrar su cumpleaños número N con una fiesta extravagante en su fortaleza intergaláctica. Para ello, ha encargado a sus pequeños robots ayudantes la tarea de preparar montañas de "Zurgitos", unos dulces mágicos que solo se pueden apilar en cantidades superiores a 2.

Cada Zurgito tiene un poder mágico diferente, representado por un número natural mayor que 2. Los pequeños robots necesitan determinar cuántas maneras hay de apilar los Zurgitos de modo que la suma de sus poderes mágicos sea exactamente N. Si hay demasiadas formas, los robots se confundirán y la fiesta se retrasará. Por lo tanto, necesitan encontrar el número de maneras posibles, módulo 100000007, para evitar un colapso del sistema de cálculo robótico.

Así que, tu tarea, aspirante a aprendiz de mago robótico, es ayudar a los robots de Zurg a resolver este problema: dado un número entero N (el número de unidades de poder mágico total que necesita Zurg para su fiesta), ¿cuántas secuencias de números naturales mayores que 2 suman N? Recuerda que el resultado debe ser modulo 100000007 para evitar un desbordamiento en el procesador de sus pequeños cerebros robóticos.

Límites

N: 1 <= N <= 200000

Subtareas

Subtarea 1: 1<=N<=100.

Subtarea 2: 1<=N<=10000.

Subtarea 3: 1<=N<=200000.

Entrada

En única línea de la entrada solamente aparecerá el valor de N.

Salida

La cantidad de secuencias que cumplen con la condición mencionada módulo 100000007.

Ejemplos

Entrada 1:

5

Salida 1:

1

Entrada 2:

7

Salida 2:

3