Zadanie

Jašteričie schodisko

Počet bodov: 80

Znovu ste vytiahli zbožňovanú hru hady a rebríky. Aktuálne síce každý sedíte oddelene a nemôžete sa ju spolu zahrať, ale šmýkať sa po hadoch a rebríkoch je zábava aj osamote! A keďže vás nikto nekontroluje, tak nemusíte ani házdať kockou a môžete sa iba voziť hore a dole a dole a hore po rebroch a hadíkoch koľko len budete vládať (a vládať teda budete veľa). Hracia plocha má 9 poschodí očíslovaných od 1 po 9 a po rebríkoch a hadákoch sa dá dostať takmer z každého poschodia na každé iné. Nanešťastie sú už niektoré hady až príliš vyšmýkané a niektoré rebríky už príliš ojazdené, a teda sú vozovky medzi poschodiami ktorých súčet čísel je štvorec z bezpečnostných dôvodov uzatvorené. Stále je však viac ako 80% trás funkčných, takže zábavy by ste mali mať habadej. Teraz sa ale naskytá ale naozaj že mimoriadne fascinujúca otázka toho, koľkými spôsobmi sa dá po tejto hracej ploche cestovať na určitý počet krokov. A keďže vás nikto nekontroluje, tak začať môžete na ľubovoľnom poschodí.

Vstup a výstup

Na prvom riadku vstupu máte číslo \(0 \leq Q \leq 100\), počet otázok. Nasleduje \(Q\) riadkov, na každom z nich jedno číslo \(2 \leq N \leq 10^{18}\) označujúce počet poschodí ktoré chcete navštíviť.

Na výstup vypíšte \(Q\) riadkov, na každom z nich odpoveď na otázku ku prislúchajúcemu riadku modulo \(10^9+7\).

Príklady

Input:

2
3
2

Output:

501
67