RoAlgo Contest #6 | Divizibilitate

Simon learned the divisibility criteria yesterday at school, and being a very smart student, Georgescu gave him an interesting problem he had been thinking about since his youth.

Task

Given the set of digits $M = \{ 1, 6, 8, 9 \}$, answer $Q$ questions of the form:
How many numbers with $N$ digits formed only from the digits in set $M$ have a remainder of $X$ when divided by $3$.

Input data

The first line contains the number $Q$, and the next $Q$ lines contain two natural numbers $N$ and $X$.

Output data

Print $Q$ natural numbers, each on a new line, representing the answer to each question in order.

Constraints and clarifications

• Since the answer can be very large, Simon will only tell Georgescu the remainder when it is divided by $10^9 + 7$.
• $1 \leq N \leq 10^{18}$.
• $1 \leq Q \leq 100 \ 000$.
• Clearly, $0 \leq X \leq 2$.

Example

stdin

3
2 0
3 1
5 2

stdout

6
21
341

Explanation

For $N = 2$ and $X = 0$, the convenient numbers are: $18$, $81$, $66$, $99$, $69$, $96$.
There are $6$ numbers with $2$ digits formed from the digits in set $M$ that are divisible by $3$.
The remainder of $6$ divided by $10^9 + 7$ is $6$.