6. Váľanie hypergúľ

“Mohol by si ísť kúpiť teplé rožky do obchodu pls?” dožadovala sa matka, “Rada by som čoskoro konzumovala raňajky!” “Ach jaj,” povzdychol som si, ale nie nahlas, iba v mysli. Nadmieru ma kokoší, keď ma niekto vyrušuje počas ranného online Krúžku Sústredeného Pozerania Tiktoku.

Cesta do obchodu nie je dlhá, ale tak či tak sa ju oplatí skrátiť crossom cez lúky a iné trávnaté plochy. Každých ušetrených 10 sekúnd je jeden pozretý BimBam navyše. Brodím sa vysokým porastom, ale čo to? “Nebodaj je to Scarabeus Multidimensionalis?!” zhíknem pošepky. Tento druh chrobáčika intímne poznám, totiž, pozeral som o ňom 30 minútový dokumentárny film. Dospelé jedince tejto živočíšnej triedy si vaľkajú vlhké guľky potravy do ktorých nakladú vajíčka, z ktorých sa vyliahnu larvy. Tento konkrétny model hlavohrudca však navyše využíva obranný mechanizmus viacdimenzionálnych hyperguliek na zmätanie predátorov. V tomto prípade to má však nežiadaný efekt vyvolania extrémneho záujmu z mojej strany.

Keď som sa znova uvedomil, všimol som si, že sa trochu stmieva. Zdá sa, že som vcelku veľkú časť dňa strávil podrobným skúmaním týchto nezvyčajných guľôčok. Asi už nebudú mať teplé rožky. Nebol to však premárnený čas! Všimol som si, že vnútro guliek prekypuje životom. Vyliahnuté larvy sa v nich hýbu hore-dole v stovkách dimenzií. Častokrát sa stane, že sa vydajú na obrovské dobrodružstvo len aby nakoniec skončili na tom istom mieste, kde začali. Kvôli rokom súťaží, sústredení a iné, mi z mysle reflexívne vyšplechla otázka: “Koľko takýchto rôznych bezvýznamných dobrodružstiev môžu absolvovať?”

Jóój, ale už ma rozbolel čobrdík a nechcem zmeškať večerníček,¹ tak čo keby ste na to odpovedali vy?

Úloha

Na lúke som stretol veľa guliek rôznych dimenzionalít, každú z nich som nejaký čas sledoval. V guľke je larva, ktorá sa neustále hýbe – každú sekundu sa pomotká v smere jednej dimenzie o jednotku vzdialenosti. Guľky sú v porovnaní s larvami omnoho väčšie, takže sa nikdy nestane že by sa prekopali ku okraju.

Pozíciu v \(D\)-dimenzionálnom priestore vieme zapísať ako zoznam \(D\) súradníc, teda \(D\) celých čísel. Larvy sú jednoduché tvory, teda sa iba rozhodnú kam sa chcú pohnúť a následne sa jednu sekundu hýbu rovnakou rýchlosťou rovnakým smerom v práve jednej dimenzii. Potom zastanú, hlboko sa zamyslia a proces opakujú. Za jednu sekundu sa teda vedia dostať do miest, ktoré sa od ich aktuálnej pozície líšia v práve jednej súradnici o práve \(1\).

Pre každú guľku ma zaujíma, koľkými rôznymi spôsobmi sa vie larva za stanovený čas prevandrovať na miesto, z ktorého začala.

Formát vstupu

Na vstup vstúpi počet guliek na lúke \(G\), následne nasleduje \(G\) riadkov, na \(i\)-tom riadku dve čísla – počet dimenzií \(d_i\) a počet sekúnd \(c_i\).

Formát výstupu

Na výstup vypíšte \(G\) riadkov, na \(i\)-tom riadku vypíšte odpoveď pre \(i\)-tu guľku modulo \(10^9+7\).

Obmedzenia

Vstupy budú rozdelené do 4 sád. Každá sada bude hodnotená 2 bodmi. Platia v nich nasledujúce obmedzenia:

Príklad

Input:

4
1 0
1 2
2 1
3 4

Output:

1
2
0
90