Liczby Fibonacciego
Mając daną liczbę N oblicz N-tą liczbę fibonacciego modulo 1000000007 = 10^9 +7
Input
W pierwszym wierszu liczba testów T<=100.
W następnych T liniach liczby Ni
Ni<=10^9
Output
Dla każdego testu w osobnej linii Ni-ta liczba ciągu fibonacciego modulo 10^9+7
Example
Input:
2
10
10000
Output:
55
271496360