Zadanie

Klik, klik, klik

Počet bodov: 85

Ajo pri svojich potulkoch sibírskou púštinou nedávno naďabil na bunker s pootverenými dverami.

Zasvietil si mobilom, a uvidel zmrazeného kostlivca ležiaceho na zemi s papierom v ruke.

“No kto by si dával tú námahu dovláčiť sem kostlivca”, krúti hlavou neveriacky Ajo.

Položil som život aby som ich zastavil. Za žiadnu cenu sa nesmie dostať do nesprávnych rúk. Toto zariadenie množí nezastaviteľný vírus. Nezapínajte ho!.

“Tento nápis ma nevie zastaviť, keďže neviem čítať!” uškrnul sa Ajo, berúc srandovnú zábavku s veľkým červeným gombíkom z kostlivcovej ruky…

Úloha

Tajomné zariadenie v sebe množí vírus.

Po prvých štyroch stlačeniach vytvorí \(1, 2, 3, 5\) kópii vírusov. Každým ďalším kliknutím sa vírusy rozmnožia, a to tak, že všetky vírusy vytvorené posledným, predposledným, a predpredpredposledným kliknutím vytvoria jednu svoju kópiu.

Zistite, koľko je na svete vírusov potom, čo Andrej klikne gombík \(X\) krát.

Vstup a výstup

V prvom riadku vstupu je číslo \(1 \leq T \leq 1000\) - koľko otázok pre vás máme.

V každom z ďalších \(T\) riadkov je celé číslo \(4 \leq X \leq 10^{10}\).

Pre každé \(X\) zrátajte, koľko vírusov je na svete. Keďže ich môže byť fakt veľa, vypíšte len jeho zvyšok po delení \(10^9+7\).

V prvej zo štyroch sád je \(X \leq 10^6\). V druhej je zasa \(T = 1\).

Príklady

Input:

3
7
5
47

Output:

64
20
349633386

V piatom kliknutí sa rozmnožia vírusy z prvého, tretieho a štvrtého, bude ich teda 1+3+5 = 9. Spolu so zvyšnými jedenástimi ich je teda 20.