AlgoLiga 2018

Zbliżają się urodziny Jasia na które Jasio zażyczył sobie nowy komputer na którym mógłby odpalić najnowsze gry. Niestety tata Jasia bogaczem nie jest, dlatego zaproponował Jasiowi układ. Dał mu zadanie, i jeśli uda mu się je rozwiązać w ciągu tygodnia to dostanie wymarzony komputer. Motywacja zdziałała cuda i Jasio już pierwszego dnia w pamięci rozwiązał to zadanie. Czy jesteś w stanie powtórzyć jego osiągnięcie ? Jako, że Ty po rozwiązaniu tego zadania nowego komputera nie dostaniesz to dla ułatwienia wystarczy, że napiszesz program który to zadanie rozwiąże. Oto ono:

Dla danego n podaj wartość powyższego wyrażenia modulo 10⁹+7.

Wejście

W pierwszej linii wejścia znajduje się liczba testów t (1 ≤ t ≤ 100).

W każdej z kolejnych t linii znajduje się jedna liczba n (1 ≤ n ≤ 10⁹).

Wyjście

Dla każdej liczby n należy wypisać wynik wyrażenia modulo 10⁹+7.

Przykład

Wejście:
5
1
3
5
7
9

Wyjście:
1
45
3982
964360
436228163