G. ABC
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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!!

Input

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}$$$

Output

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

Example
Input
3
2 1
2 2
3 2
Output
0
4
6