maxhits

Andrei, Bogdan și Claudia joacă un joc cu $N$ ținte așezate pe un rând și cu un pistol de vopsit de putere $K$.

Inițial, fiecare țintă este vopsită în alb și are scris pe ea numărul $0$. O țintă se numește liberă dacă este albă și are scris pe ea numărul $0$.

Jocul se desfășoară în mutări care lovesc cel mult $K$ ținte consecutive. La a $i$-a mutare, toate țintele lovite de acea mutare sunt vopsite în culoarea mutării, iar pe fiecare dintre ele se scrie numărul $i$. Bogdan este interesat doar de culorile țintelor. El vrea să știe numărul $B$ de colorări diferite care pot apărea după un joc terminat în care numărul maxim posibil este scris pe cel puțin o țintă. Două colorări sunt diferite dacă există cel puțin o țintă care are culori diferite în cele două colorări.

Există trei tipuri de mutări: Albastre, Galbene și Roșii:

• O mutare Albastră alege exact $K$ ținte consecutive. O astfel de mutare este validă dacă toate țintele alese sunt libere, iar ținta imediat din stânga și ținta imediat din dreapta există și sunt, de asemenea, libere.
• O mutare Galbenă este permisă doar dacă nu mai există nicio mutare Albastră validă. Ea alege câteva ținte libere consecutive și le vopsește în galben. Țintele alese trebuie să aibă o țintă liberă imediat în stânga și o țintă liberă imediat în dreapta, iar mutarea trebuie să fie maximală: nu poate fi extinsă nici la stânga, nici la dreapta păstrând această proprietate. Echivalent, o mutare Galbenă acționează asupra unui bloc maximal de ținte libere de lungime între $3$ și $K + 1$ și vopsește toate țintele din acel bloc, cu excepția primei și ultimei.
• O mutare Roșie este permisă doar dacă nu mai există nicio mutare Albastră sau Galbenă validă. Ea alege un bloc maximal de ținte libere consecutive și îl vopsește în întregime în roșu. O mutare Roșie lovește întotdeauna fie $1$, fie $2$ ținte.

Jocul se termină când nu mai există nicio țintă liberă.

Andrei este interesat de cel mai mare număr $A$ care poate fi scris pe o țintă după terminarea jocului.

Bogdan este interesat doar de culorile țintelor. El vrea să știe numărul $B$, câte colorări diferite pot apărea după un joc terminat în care numărul maxim posibil este scris pe cel puțin o țintă. Două colorări sunt diferite dacă există cel puțin o țintă care are culori diferite în cele două colorări.

Claudia este interesată doar de numerele scrise pe ținte. Ea vrea să știe numărul $C$, câte numerotări diferite pot apărea după un joc terminat în care numărul maxim posibil este scris pe cel puțin o țintă. Două numerotări sunt diferite dacă există cel puțin o țintă care are numere diferite în cele două numerotări.

Cerință

Ajutați-i pe cei trei să își afle numerele lor, $A$, $B$ și respectiv $C$. Deoarece răspunsurile pentru Bogdan și Claudia pot fi foarte mari, calculați-le modulo $1 \ 000 \ 000 \ 007$. Atenție! Numărul $A$ trebuie calculat fără niciun modulo.

Date de intrare

Pe prima linie a fișierului de intrare maxhits.in se află $T$, numărul de scenarii de joc la care va trebui să răspundeți. Fiecare dintre următoarele $T$ linii conține câte două numere, $N$ și $K$, în această ordine și cu semnificația din enunț.

Date de ieșire

În fișierul de ieșire maxhits.out se vor afișa $T$ linii fiecare conținând $3$ numere, al $i$-lea triplet reprezentând răspunsul pentru $A$, $B$ și $C$, în această ordine, pentru al $i$-lea scenariu de joc.

Restricții și precizări

• $1 \leq T \leq 100 \ 000$
• $K \leq N \leq 10^{11}$
• $3 \leq K \leq 500 \ 000$
• $1 \leq \frac{N}{K} \leq 500 \ 000$
• Pentru fiecare test, dacă toate valorile $A$-urilor sunt corecte se va acorda $40\%$ din punctaj.
• Pentru fiecare test, dacă toate valorile $B$-urilor sunt corecte se va acorda $30\%$ din punctaj.
• Pentru fiecare test, dacă toate valorile $C$-urilor sunt corecte se va acorda $30\%$ din punctaj.
• Atenție! Trebuie afișate răspunsuri (posibil incorecte) pentru toate cele trei numere $A$, $B$ și $C$ pentru obținerea punctajelor parțiale.

Exemplu

maxhits.in

3
5 3
20 7
123456789 54321

maxhits.out

3 1 2
7 13 624
9091 668672468 892007695

Explicație

Pentru primul exemplu, avem $N = 5$ și $K = 3$.

Singura mutare Albastră validă este pe țintele $2$, $3$, $4$, deoarece acestea sunt trei ținte consecutive libere și au câte o țintă liberă imediat în stânga și în dreapta.

După această mutare, mai rămân libere doar țintele $1$ și $5$. Nu mai există nicio mutare Albastră sau Galbenă validă, deci cele două ținte rămase vor fi lovite prin mutări Roșii. Ele pot fi lovite în două ordini diferite.

În ambele stări, cel mai mare număr scris pe o țintă este $3$, deci $A = 3$.

Există o singură colorare posibilă: țintele $2$, $3$, $4$ sunt Albastre, iar țintele $1$ și $5$ sunt Roșii. Deci $B = 1$.

Există două numerotări posibile, deoarece cele două mutări Roșii pot fi făcute în două ordini diferite. Deci $C = 2$.

Pentru al doilea exemplu, unde $N = 20$ și $K = 7$, iată o stare finală posibilă care atinge valoarea maximă $A = 7$.