← 返回题目列表

Codeforces · 2033/F

F. 小介的树懒

中文机器翻译题面 查看原题

小介太懒了。他不会给你任何传说,只会给你任务:

斐波那契数定义如下:

- $$$f(1)=f(2)=1$$$。
- $$$f(n)=f(n-1)+f(n-2)$$$ $$$(3\le n)$$$

由于这个数字可能太大,所以以 $$$10^9+7$$$ 为模输出。

例如:$$$G(3,2)=9$$$,因为能被 $$$2$$$ 整除的 $$$3$$$-rd 斐波那契数是 $$$34$$$。 $$$[1,1,\textbf{2},3,5,\textbf{8},13,21,\textbf{34}]$$$。

输入

输入数据的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

第一行也是唯一一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 10^{18}$$$, $$$1 \le k \le 10^5$$$)。

保证所有测试用例的 $$$k$$$ 总和不超过 $$$10^6$$$。

输出

对于每个测试用例,输出唯一的数字:$$$G(n,k)$$$ 取模$$$10^9+7$$$ 得到的值。

示例

输入 #1

3
3 2
100 1
1000000000000 1377

输出 #1

9
100
999244007