Codeforces Round 981 (Div. 3) |
---|
Finished |
Kosuke is too lazy. He will not give you any legend, just the task:
Fibonacci numbers are defined as follows:
As this number can be too big, output it by modulo 109+7.
For example: G(3,2)=9 because the 3-rd Fibonacci number that is divisible by 2 is 34. [1,1,2,3,5,8,13,21,34].
The first line of the input data contains a single integer t (1≤t≤104) — the number of test cases.
The first and only line contains two integers n and k (1≤n≤1018, 1≤k≤105).
It is guaranteed that the sum of k across all test cases does not exceed 106.
For each test case, output the only number: the value G(n,k) taken by modulo 109+7.
33 2100 11000000000000 1377
9 100 999244007
Name |
---|