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 <= t <= 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 <= n <= 10^9)$ $(1 <= k <= m i n (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$.
## Input
First line contains one integer $t$ $(1 <= t <= 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 <= n <= 10^9)$ $(1 <= k <= m i n (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$.
[samples]
**Definitions**
Let $ t \in \mathbb{Z} $ be the number of test cases.
For each test case, let $ n, k \in \mathbb{Z} $ with $ 1 \leq n \leq 10^9 $, $ 1 \leq k \leq \min(n, 10^5) $.
Let $ \Sigma = \{A, B, C\} $ be the alphabet.
A string $ s \in \Sigma^n $ is *beautiful* if for every contiguous substring of length $ k $, the number of $ A $'s plus the number of $ B $'s equals the number of $ C $'s.
**Constraints**
1. $ 1 \leq t \leq 10^5 $
2. $ \sum_{\text{all test cases}} k \leq 10^6 $
**Objective**
For each test case, compute the number of beautiful strings of length $ n $ over $ \Sigma $, modulo $ 1000000007 $.
**Key Insight**
For every substring of length $ k $, let $ c $ be the count of $ C $'s, then $ A + B = c $, and since $ A + B + C = k $, we have $ c = k - c \Rightarrow 2c = k \Rightarrow k \text{ even} $.
Thus, if $ k $ is odd, no such string exists → answer is $ 0 $.
If $ k $ is even, then in every window of length $ k $, exactly $ k/2 $ characters are $ C $, and $ k/2 $ are $ A $ or $ B $.
This forces a periodic structure: for the condition to hold for all overlapping windows of length $ k $, the string must be periodic with period $ k $, and within each block of $ k $, exactly $ k/2 $ positions are $ C $, and the rest are $ A/B $.
But more strongly: consider two overlapping windows $ s[i..i+k-1] $ and $ s[i+1..i+k] $. Their difference implies $ s[i] = s[i+k] $.
Thus, the entire string must be periodic with period $ k $: $ s[i] = s[i \bmod k] $ for all $ i $.
Therefore, the string is determined by its first $ k $ characters, which must satisfy:
- Exactly $ k/2 $ of them are $ C $,
- The remaining $ k/2 $ are either $ A $ or $ B $.
Then the full string of length $ n $ is just the repetition of this $ k $-length block.
So:
- If $ k $ is odd → answer = 0
- If $ k $ is even →
- Choose $ k/2 $ positions out of $ k $ to place $ C $: $ \binom{k}{k/2} $
- Each of the remaining $ k/2 $ positions can be $ A $ or $ B $: $ 2^{k/2} $
- Total for one period: $ \binom{k}{k/2} \cdot 2^{k/2} $
- Since the string of length $ n $ is determined by the first $ k $ characters (periodic), the total number of beautiful strings is exactly $ \binom{k}{k/2} \cdot 2^{k/2} $
**Final Objective**
For each test case:
$$
\text{Answer} =
\begin{cases}
0 & \text{if } k \text{ is odd} \\
\binom{k}{k/2} \cdot 2^{k/2} \mod 1000000007 & \text{if } k \text{ is even}
\end{cases}
$$