vrajitoare

Un copil năzdrăvan mergea prin parc, iar deodată a apărut un urs în cale. Din fericire, o vrăjitoare foarte batrână a apărut și a salvat copilul din ghearele ursului. Totuși, ajutorul oferit de vrăjitoare nu e necondiționat. Pentru a se putea revanșa, vrăjitoarea a adus piticii ei și i-a zis copilului:

"Uită-te atent la pitici. Fiecare dintre ei are scris trei numere pe frunte. Să notăm numerele piticului $i$ cu $v_i$, $b_i$ și $x_i$. Considerăm numărul $m_i$, care este egal cu numărul de numere gadfadăriene de la $0$ la $v_i$. Poate te întrebi ce este acela un număr gadfadărian. Ei bine, este un număr care are $x_i$ de $1$ în reprezentarea lui în baza $b_i$. Eu vreau să știu $m_i$. Totuși, voi fi generoasă astăzi și îți cer doar rezultatul modulo $10^9 + 7$."

Ajut-o pe vrăjitoare să găsească răspunsul la întrebare!

Date de intrare

Pe prima linie se află un număr natural $n$, reprezentând numarul de pitici.

Pe urmatoarele $n$ linii, se afla numerele de pe frunțile piticilor, numărul $v_i$ reprezentând numărul scris pe fruntea piticului $i$, $b_i$ reprezintă baza la care face referire vrăjitoarea, iar $x_i$ reprezintă numărul de $1$ din baza $b_i$ de care avem nevoie. Numărul este dat în baza $b_i$.

Date de ieșire

Pentru fiecare pitic, se va afișa pe câte o linie separată răspunsul cerut, reprezentând valoarea lui $m_i$ modulo $10^9 + 7$.

Restricții și precizări

• $1 \leq n \leq 100$;
• $v_i$ are cel mult $10^5$ cifre în baza $b_i$;
• $2 \leq b_i \leq 10$;
• $0 \leq x_i \leq |v_i|$;

Exemplul 1

stdin

6
99 10 1
1110100011 2 3
1110100011 2 2
12103 5 2
681 9 0
999 10 2

stdout

18
120
45
219
377
27

Explicație

Pentru primul exemplu, numerele valide sunt $1$, numerele de la $10$ la $19$ cu exceptia lui $11$ si numerele $21$, $31$, $\dots$, $91$.