Problem description


Króliczki Fibonacciego
(kroliczki-fibonacciego)
Limit pamięci: 256 MB
Limit czasu: 6.00 s

Pan Fibonacci, hodowca królików, zauważył pewną zależność związaną z reprodukcją swoich zwierząt. Każda para królików (samca i samiczki) co miesiąc rodzi nową parę królików. Nowo urodzona para musi odczekać miesiąc, zanim będzie zdolna do reprodukcji (która trwa kolejny miesiąc). W takim razie, gdyby hodowca miał tylko jedną parę młodych królików, to po miesiącu nadal miałby jedną parę, lecz po dwóch miesiącach byłyby to już dwie pary, po trzech miesiącach trzy pary itd.

Pan Fibonacci zaczął się zastanawiać, ile par królików miałby po N miesiącach? Pomóż mu i napisz program, który obliczy tę liczbę. Jako, że odpowiedź może być bardzo duża, odpowiedź należy podać modulo 109 + 7.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna T oznaczająca liczbę zestawów testowych. W kolejnych T wierszach znajdują się opisy kolejnych zestawów testowych. i-ty z nich składa się z jednej liczby całkowitej Ni.

Wyjście

Należy wypisać T wierszy. i-ty z nich powinien określać liczbę par królików po Ni miesiącach modulo 109 + 7.

Ograniczenia

1 ≤ T ≤ 200 000, 1 ≤ Ni ≤ 1018.

Przykład

Wejście Wyjście
5
1
2
5
6
10
1
1
5
8
55