ACG

Team ACG is a programming contest team made up of A, C, and G. Today they are preparing for the upcoming ICPC.

The contest ACG solves today has $N$ problems. ACG is a very strong team, so they can solve every problem there is.

To make practice feel like the real thing, they use a single computer. Each problem can be solved by any one of A, C, and G.

The order of the problems often has nothing to do with difficulty, so most other teams do not solve them in order. ACG solves everything anyway, so they always work through the problems in the given order.

Now they have to decide who solves each problem. Two people never work on one problem together, and exactly one person takes each problem. Write a program that counts the ways to pick the solver of every problem so that all of the conditions below hold.

• A likes the integer $k$ very much. The number of problems A solves must be a multiple of $k$.
• C is a person who likes to rest, so C cannot solve two or more problems in a row.
• G is not a person who likes solving problems. G only has to solve at least one problem.

When $k = 0$, the only multiple of $0$ is $0$, so A solves no problem at all.

The first line contains the number of test cases $T$ ($1 \le T \le 50$). Each test case is a single line holding $N$ and $k$ separated by a space. ($1 \le N \le 10^{18}$, $0 \le k \le 10$)

For each test case, print the number of ways to pick the solver of every problem, modulo $10000007$, one per line.