Wstęp do programowania w C++

Łańcuszek choinkowy

Jasiu przystroił choinkę, pozostał mu już tylko ostatni element dekoracji - łańcuszek choinkowy, którego nie ma. Postanowił, że zrobi srebrno złoty o długości n, w którym żadne dwa sąsiednie ogniwa nie będą w kolorze złotym. Tu powstaje nurtujące Jasia pytanie, na ile sposobów może taki łańcuszek wykonać?

Wejście
Wejście składa się z góry nieznanej liczby wierszy (max 10⁵). W każdym wierszu znajduje się jedna liczba n (2 ≤ n ≤ 10⁹) - liczba ogniw łańcuszka.

Wyjście
Dla każdego zapytania w osobnym wierszu należy wypisać jedną liczbę, resztę z dzielenia liczby sposobów wykonania łańcuszka przez 1000000007.

Przykład

Wejście
4
10

Wyjście
8
144