友情提示：380元/半年，儿童学编程，就上码丁实验室。
【题目描述】
设为 $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)$。每一维从$1sim 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$。