小介太懒了。他不会给你任何传说,只会给你任务:
斐波那契数定义如下:
- $$$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