一个dp，本来是要用矩阵快速幂的，但由于学姐把范围砍了，所以只要普通的快速幂就行了

QAQorz一回到长沙就直奔汉堡王，已知小食的美味度是111，汉堡的美味度是mmm，QAQorz一共能吃nnn美味度的东西，请问QAQorz吃一次汉堡王有几种不同的搭配方案？

关于方案：如果两个方案吃汉堡和小食的先后顺序不同，则称这两种方案是不同的

具体来说：假设一份小食用一个111表示，一个汉堡用mmm个000表示。当m=2m=2m=2时，先吃一份小食再吃一个汉堡再吃一份小食，方案表示为100110011001，两个方案不同当且仅当两个010101串是不同的。

Input

第一行一个数ttt，表示t(1≤t≤15)t(1\leq t\leq15)t(1≤t≤15)组数据。接下来ttt行，每行两个数表示nnn和mmm，1≤n≤2e51\leq n \leq 2e51≤n≤2e5, 1≤m≤101\leq m \leq 101≤m≤10

Output

方案数，输出答案对100000007（1e8+7）取模.

Sample Input 1

22 24 2

Sample Output 1

25

Hint

样例解释：

5种方案分别为：

吃4份小食，表示为1111

先吃一个汉堡再吃2份小食，表示为0011

先吃一份小食再吃一个汉堡再吃一份小食，表示为1001

先吃两份小食再吃一个汉堡，表示为1100

吃两个汉堡，表示为0000

所以方案数为5

#include
     
      using namespace std;typedef long long ll;const int maxn=2e5+7;const ll mod=1e8+7;ll dp[maxn];ll quickpow(ll base,ll mi){    ll ans=1;    while(mi)    {        if(mi&1)            ans=ans*base%mod;        base=base*base%mod;        mi>>=1;    }    return ans;}int main(){    int t;    cin>>t;    while(t--)    {        int n,m;        cin>>n>>m;        if(m==1)        {            ll ans=quickpow(2,n);            cout<
      
       <