D

D. Числа Фибоначчи для взрослых

Гоша практикуется в динамическом программировании — он хочет быстро считать числа Фибоначчи.

Напомним, что числа Фибоначчи определены как последовательность F_n, n = 0,1. F₀ = F₁ = 1, F_n = F_n-1 + F_n-2, n ≥ 2.

Помогите Гоше решить эту задачу

Формат ввода

В единственной строке дано целое число n (0 ≤ n ≤ 10⁶).

Формат вывода

Вычислите значение F_n по модулю 10⁹ + 7 и выведите его.

Пример 1

5

8

Пример 2

2

2

Пример 3

10

89