题目描述

设为 $F(i)$斐波那契数列的第$i$项，其中 $F(1)=1,F(2)=1,F(i)=F(i-1)+F(i-2)$。 给定 $n,k$，请你求出一个由斐波拉契数列中元素构成的$k$维超立方体$A$内所有元素的和。 $A$为一个$n×n×n×…×n$($k$个$n$连乘)的$k$ 维超立方体。 $A(i_1,i_2,…,i_k )=F(i_1+i_2+⋯+i_k-k+1)$。每一维从$1\sim n$编号，即$1≤i_1,i_2,…,i_k≤n$。 由于元素之和可能很大，所以最后答案模$10^9+7$。

输入

输入数据包含多个测试点，第一行一个正整数$T$表示数据组数。 接下来T行，每行两个正整数$n,k$，意义见题目描述。

输出

对于每组数据，输出一行一个整数表示答案。

输入样例

3
2 2
4 1
1 3

输出样例

5
7
1

提示

【数据规模与约定】 对于20%的数据，$n,k≤5$。 另有20%的数据，$k=1$。 对于60%的数据，$k≤100$。 对于100%的数据，$T≤100,n,k≤10^9$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。