405683: GYM102035 G ABC

Bashar was learning the alphabets, in the last class he learned letters A,B,C. After that he decided to go home. On his way home, he was thinking of how many strings of length $$$n$$$ that are made up of letters A,B,C are beautiful. Beautiful strings are strings such that for all substrings of length $$$k$$$, the number of A's + number of B's is equal to the number of C's.

Bashar couldn't solve the problem and fell asleep, can you solve them for him before he wakes up!!

First line contains one integer $$$t$$$ $$$(1 \leq t \leq 10 ^ {5})$$$ which is the number of test cases.

For every test case you are given two integers $$$n$$$ and $$$k$$$ on a line $$$(1 \leq n \leq 10^{9})$$$ $$$(1 \leq k \leq min(n,10^{5}))$$$.

Sum of $$$k$$$ between all test cases will not exceed $$$10^{6}$$$

For every test case print the answer on a line, since the answer can be very large print it modulo $$$1000000007$$$.

3
2 1
2 2
3 2

0
4
6