Cerința

Avem la dispoziție oricâți căței și oricâte pisici, câte așezări ale acestora în linie dreaptă de lungime n există astfel incât să nu avem o pisică între 2 căței și configurația să înceapă cu un câine și să se termine cu o pisică? Răspunsul se afișează modulo $10^9+7$.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Programul va afișa pe ecran răspunsul.

Restricții și precizări

• 2 ≤ n ≤ 1.000.000.

Exemplu:

Intrare

3

Ieșire

2

Explicație

Configurațile sunt:
CPP
CCP