Divizibilitate

Șimon a învățat ieri la școală criteriile de divizibilitate și fiind un elev foarte deștept Georgescu i-a dat o problemă interesantă la care se gândea din tinerețe.

Cerință

Se dă mulțimea de cifre $M = \{ 1, 6, 8, 9 \}$.

Să se răspundă la $Q$ întrebări de forma:
Câte numere de $N$ cifre formate doar din cifrele mulțimii $M$ au restul la împărțirea cu $3$, valoarea $X$.

Date de intrare

Pe prima linie se va afla numărul $Q$ și pe următoarele $Q$ linii câte două numere naturale $N$ și $X$.

Date de ieșire

Se vor afișa $Q$ numere naturale pe câte o linie, reprezentând răspunsul la fiecare întrebare, în ordine.

Restricții și precizări

• Pentru că răspunsul poate fi foarte mare, Șimon nu îi va spune lui Georgescu decât restul împărțirii acestuia la $10^9 + 7$.
• $1 \leq N \leq 10^{18}$.
• $1 \leq Q \leq 100 \ 000$.
• Evident, $0 \leq X \leq 2$.

Exemplu

stdin

3
2 0
3 1
5 2

stdout

6
21
341

Explicație

Pentru $N = 2$ și $X = 0$ numerele convenabile sunt: $18$, $81$, $66$, $99$, $69$, $96$.
Sunt $6$ numere de $2$ cifre formate din cifrele mulțimii $M$ divizibile cu $3$.
Restul împărțirii lui $6$ la $10^9 + 7$ este $6$.