{"raw_statement":[{"iden":"statement","content":"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.\n\nBashar couldn't solve the problem and fell asleep, can you solve them for him before he wakes up!!\n\nFirst line contains one integer $t$ $(1 <= t <= 10^5)$ which is the number of test cases.\n\nFor 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))$.\n\nSum of $k$ between all test cases will not exceed $10^6$\n\nFor every test case print the answer on a line, since the answer can be very large print it modulo $1000000007$.\n\n"},{"iden":"input","content":"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$"},{"iden":"output","content":"For every test case print the answer on a line, since the answer can be very large print it modulo $1000000007$."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ t \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case, let $ n, k \\in \\mathbb{Z} $ with $ 1 \\leq n \\leq 10^9 $, $ 1 \\leq k \\leq \\min(n, 10^5) $.  \nLet $ \\Sigma = \\{A, B, C\\} $ be the alphabet.  \nA 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.\n\n**Constraints**  \n1. $ 1 \\leq t \\leq 10^5 $  \n2. $ \\sum_{\\text{all test cases}} k \\leq 10^6 $  \n\n**Objective**  \nFor each test case, compute the number of beautiful strings of length $ n $ over $ \\Sigma $, modulo $ 1000000007 $.  \n\n**Key Insight**  \nFor 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} $.  \nThus, if $ k $ is odd, no such string exists → answer is $ 0 $.  \n\nIf $ k $ is even, then in every window of length $ k $, exactly $ k/2 $ characters are $ C $, and $ k/2 $ are $ A $ or $ B $.  \nThis 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 $.  \n\nBut 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] $.  \nThus, the entire string must be periodic with period $ k $: $ s[i] = s[i \\bmod k] $ for all $ i $.  \n\nTherefore, the string is determined by its first $ k $ characters, which must satisfy:  \n- Exactly $ k/2 $ of them are $ C $,  \n- The remaining $ k/2 $ are either $ A $ or $ B $.  \n\nThen the full string of length $ n $ is just the repetition of this $ k $-length block.  \n\nSo:  \n- If $ k $ is odd → answer = 0  \n- If $ k $ is even →  \n  - Choose $ k/2 $ positions out of $ k $ to place $ C $: $ \\binom{k}{k/2} $  \n  - Each of the remaining $ k/2 $ positions can be $ A $ or $ B $: $ 2^{k/2} $  \n  - Total for one period: $ \\binom{k}{k/2} \\cdot 2^{k/2} $  \n  - 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} $\n\n**Final Objective**  \nFor each test case:  \n$$\n\\text{Answer} =\n\\begin{cases}\n0 & \\text{if } k \\text{ is odd} \\\\\n\\binom{k}{k/2} \\cdot 2^{k/2} \\mod 1000000007 & \\text{if } k \\text{ is even}\n\\end{cases}\n$$","simple_statement":"Count the number of strings of length n using letters A, B, C such that in every contiguous substring of length k, the number of A’s plus B’s equals the number of C’s. Answer modulo 1000000007.","has_page_source":false}