Problem description

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 10⁹ + 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 N_i.

Wyjście

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

Ograniczenia

1 ≤ T ≤ 200 000, 1 ≤ N_i ≤ 10¹⁸.

Przykład

5
1
2
5
6
10

1
1
5
8
55