Kosuke is too lazy. He will not give you any legend, just the task: Fibonacci numbers are defined as follows: (f(1)=f(2)=1). (f(n)=f(n-1)+f(n-2)) ((3\le n)) As this number can be too big, output it by modulo (10^9+7). For example: (G(3,2)=9) because the (3)-rd Fibonacci number that is divisible by (2) is (34). (1,1,\textbf{2},3,5,\textbf{8},13,21,\textbf{34}). The first line of the input data contains a single integer (t) ((1 \le t \le 10^4)) — the number of test cases. The first and only line contains two integers (n) and (k) ((1 \le n \le 10^{18}), (1 \le k \le 10^5)). It is guaranteed that the sum of (k) across all test cases does not exceed (10^6). For each test case, output the only number: the value (G(n,k)) taken by modulo (10^9+7).