A. Фибоначчи по модулю

Числа Фибоначчи заданы так: $f_1 = f_2 = 1$, а при $n > 2$ выполнено $f_n = f_{n-1} + f_{n-2}$.

Выведите остаток от деления $f_n$ на $10^9 + 7$. Само число хранить не нужно и невозможно: у $f_{10^6}$ больше двухсот тысяч цифр.

Одна строка содержит число $n$ ($1 \le n \le 10^6$).

Одно число — остаток от деления $f_n$ на $10^9 + 7$.