Zadanie

Hranolky na MatFyze sú z nich

Počet bodov: 50

Byť programátorom môže byť ťažké. Stále niečo nefunguje, zabíjate hodiny nad nepochopiteľnými chybovými hláškami, na jedinej relevatnej stack overflow otázke autor odpovedá len ‘už som to nejak vyriešil’.

Preto sa Dávid stal farmárom. Byť farmárom je jednoduché. Zakopete zemiak, a neskôr vykopete viac zemiakov. O to jednoduchšie to pre Dávida je, že si zo svojho kódu pripravil inovatívne hnojivo, vďaka ktorému sa zemiaky rozmnožia už za jednu noc.

Presnejšie, každý zemiak sa za noc rozmnoží na \(Z\) zemiakov, a ďalšiu noc sa z každého z nich znova stane \(Z\) zemiakov, a tak ďalej.

Dávid je navyše jasnovid, a tak vie že ak by takto produkoval zemiaky príliš dlho, bolo by to podozrivé. Preto chce predávať zemiaky len \(N\) dní, a aby nezanechal žiadne stopy, tak chce aby mu po nich neostali žiadne zemiaky.

Dávid má navyše rád rutinu. Preto by chcel každé ráno vykopať a predať nejaký rovnaký počet zemiakov, \(P\); na presnej hodnote mu nezáleží, len aby to bolo konzistentné.

Dávid je navyše lenivý, a nechce sa mu sadiť veľa zemiakov. Preto ich bude sadiť iba raz, a aj vtedy chce aby počet zemiakov ktoré zasadí, \(S\), bolo čo najmenšie.

Dávid navyše pripravuje úlohy do zenitu, a tak nájdenie vhodných čísel \(P\) a \(S\) nechá na vás.

Úloha

Dané sú celé čísla \(Z\) a \(N\) - ako sa zemiaky rozmnožujú, a koľko dní chce Dávid predávať zemiaky. Dávid chce večer zasadiť nejaký čo najmenší počet zemiakov \(S\). Musí pritom platiť, že ak sa z každého zemiaku cez noc stane \(Z\) zemiakov, a každé ráno Dávid presne \(P\) z nich vykope a predá, tak to bude môcť robiť \(N\) dní, po ktorých mu neostanú žiadne zemiaky.

Nájdite čísla \(S\) a \(P\), pre ktoré sa mu to podarí. Ak existuje viacero riešení, vypíšte to s najemnším \(S\).

Vstup a Výstup

V prvom riadku je celé číslo \(T\) - počet alternatívnych realít, v ktorých Dávid pestuje zemiaky.

V každom z ďalších \(T\) riadkov sú dve čísla \(Z\) a \(N\) - ako sa zemiaky rozmnožujú, a koľko dní chce Dávid predávať zemiaky.

Pre každé \(N\) a \(Z\) vypíšte čo najmenšie \(S\) a k nemu korešpondujúce \(P\), tak, aby vedel Dávid zasadiť \(S\) zemiakov, a \(N\) krát nechat zemiaky sa rozmnožiť a následne \(P\) z nich vykopať a predať, pričom po \(N\) dňoch bude mať nula zemiakov.

Keďže tieto čísla môžu byť veľké, stačí ak ich vypíšete modulo \(10^9+7\).

Platí \(1 \leq T \leq 1000\).

V prvej sade \(2 \leq Z \leq 100\) a \(N = 1\).

V druhej \(2 \leq Z \leq 100\) a \(1 \leq N \leq 2\).

V tretej až piatej sade platí \(2 \leq Z \leq 10^5\) a \(1 \leq N \leq 10^5\).

Príklady

Input:

4
2 2
2 3
3 4
47 47

Output:

3 4
7 8
40 81
932085956 875953683

V prvej realite Dávid večer zakope 3 zemiaky. Na prvý deń ich bude 6, Dávid štyri z nich vykope a predá. Z dvoch zvyšních zemiakov sa stanú štyri, a na druhý deň ich všetky vykope a predá. Po dvoch dňoch mu teda úspešne neostali žiadne zemiaky.

Ak by chcel dávid predávať zdvojnásobujúce zemiaky tri dni, musí zakopať aspoň 7 zemiakov, a pri siedmych mu to na práve tri dni vyjde, ak každý deň predá 8.