Инженер разрабатывает систему кодовых слов длины n, состоящих только из символов 0 и 1.

Кодовое слово считается допустимым, если в нём нигде не встречаются две единицы подряд.

Требуется определить, сколько существует допустимых кодовых слов длины n. Так как ответ может быть очень большим, выведите его по модулю 1000000007.

Входные данные

В единственной строке задано целое число n (1 <= n <= 10^6).

Выходные данные

Выведите количество допустимых кодовых слов длины n по модулю 1000000007.

Ограничения

1 <= n <= 10^6

Примеры

Пример 1

Входные данные

3

Выходные данные

5

Пояснение

Для n=3 подходят 000, 001, 010, 100, 101 — всего 5.

Пример 2

Входные данные

1

Выходные данные

2

Пример 3

Входные данные

2

Выходные данные

3