Zadanie

Hašterivé sny

Počet bodov: 50

Minulú noc sa Jozefovi sníval znova ten istý sen. Keď sa na seba pozrel, videl, ako mu z tela vychádzajú dve ruky. Síce na jedného človeka nadpriemerný počet¹, ale to nebolo to surreálne pozorovanie. Ako sa tak pozeral od ramien smerom k zápästiam, na ich miestach nenašiel dlane a prsty, ale krk a znova sa vynárajúce dve ramená. Toto sa pár krát opakovalo, niekedy z krku vychádzalo iba jedno rameno, inokedy konečne prsty.

Bežný človek má dosah na vzdialenosť dĺžky jednej ruky. Jozef však v týchto snoch vďaka svojmu vzrastu dokázal dosiahnuť na mnohonásobok toho na čo bol zvyknutý. Za ten čas čo strávil v každonočných snoch a videl ako sa jeho ruky nekontrolovateľne hmýria, trasú a siahajú na všetko naokolo, zvládol odpozorovať dva kľúčové fakty: vie aký veľký má dosah a vie, že keďže je pravák, tak pre každý krk má pravé rameno aspoň taký veľký dosah ako to ľavé.

jeden príklad valídneho sna s dosahom 6 (v každom krku máme napísaný maximálny dosah)

tu zase vidíme príklad postihnutého sna - v hneď prvom krku má pravé rameno menší dosah ako ľavé

Úloha

Jozef má vo svojom sne hlavu pripevnenú ku krku. Z každého krku môžu vychádzať najviac dve ramená (ak by ich vychádzalo viac tak by to bolo nerealistické), všetky ukončené krkmi. Keďže je pravák tak pre každý krk platí, že pravé rameno má aspoň taký veľký dosah ako ľavé.

Jozef si o svojich snoch píše do denníčka, avšak človek čo sa zobudí si zo svojho sna pamätá iba veľmi málo a tak jeho denníček obsahuje iba zoznam čísel udávajúcich jeho najväčší dosah z danej noci.

Všetkých by nás zaujímalo, koľkými rôznymi spôsobmi mohli z Jozefa vychádzať jeho končatiny, tak to pre každý zápis v denníčku zistite.

Formát vstupu

Prvý riadok obsahuje číslo \(N\) - počet nocí (\(1 \leq N \leq 10^5\)). Nasleduje \(N\) riadkov, na každom riadku jedno celé číslo \(d_i\) - maximálny dosah počas \(i\)-tej noci (\(0 \leq d_i \leq 2*10^6\)).

Formát výstupu

Na výstup vypíšte \(N\) riadkov, na každom riadku jedno číslo - odpoveď na otázku pre danú noc modulo \(10^9+7\).

Príklad

Input:

2
0
1

Output:

1
2