学步园

We consider problems concerning the number of ways in which a number can be written as a sum. If the order of the terms in the sum is taken into account the sum is called a composition
and the number of compositions of n is denoted by c(n). Thus, the compositions of 3 are

• 3 = 3
• 3 = 1 + 2
• 3 = 2 + 1
• 3 = 1 + 1 + 1

So that c(3) = 4.

Suppose we denote by c(n, k) the number of compositions of n with all summands at least k. Thus, the compositions of 3 with all summands at least 2 are

• 3 = 3

The other three compositions of 3 all have summand 1, which is less than 2. So that c(3, 2) = 1.

Input

The first line of the input is an integer t (t <= 30), indicate the number of cases.

For each case, there is one line consisting of two integers n k (1 <= n <= 10⁹, 1 <= k <= 30).

Output

Output c(n, k) modulo 10⁹ + 7.

Sample Input

2
3 1
3 2

Sample Output

4
1

#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdio>

using namespace std;

#define MAX_SIZE 32

struct Matrix
{
    int size;
    long long modulo;
    long long element[MAX_SIZE][MAX_SIZE];
    void setSize(int);
    void setModulo(long long);
    Matrix operator* (Matrix);
    Matrix power(int);

};

void Matrix::setSize(int a)
{
    for (int i=0; i<a; i++)
        for (int j=0; j<a; j++)
            element[i][j]=0;
    size = a;
}

void Matrix::setModulo(long long a)
{
    modulo = a;
}

Matrix Matrix::operator* (Matrix param)
{
    Matrix product;
    product.setSize(size);
    product.setModulo(modulo);
    for (int i=0; i<size; i++)
        for (int j=0; j<size; j++)
            for (int k=0; k<size; k++)
            {
                product.element[i][j]+=element[i][k]*param.element[k][j];
                product.element[i][j]%=modulo;
            }
    return product;
}

Matrix Matrix::power(int exp)
{
    Matrix res,A;
    A=*this;
    res.setSize(size);
    res.setModulo(modulo);
    for(int i=0;i<size;i++)
        res.element[i][i]=1;
    while(exp)
    {
        if(exp&1)
            res=res*A;
        exp>>=1;
        A=A*A;
    }
    return res;
}

long long a[60];
Matrix m;
int n,k;
int main()
{
    int  cs;
    m.setModulo(1000000000+7);
    cin>>cs;
    while(cs--)
    {
        cin>>n>>k;
        m.setSize(k);
        if(k!=1){
        m.element[0][0]=1;
        m.element[0][k-1]=1;
        for(int i=1;i<k;i++)
            m.element[i][i-1]=1;
        }
        else
        {
            m.element[0][0]=2;
        }
        if(n<k)
        {
            printf("0\n");
        }
        else if(n==k)
        {
            printf("1\n");
        }
        else
        {
            a[0]=1;
            for(int i=1;i<k;i++)
                    a[i]=0;

            int pw=n-k;
            m=m.power(pw);
            long long ans=0;
            for(int i=0;i<k;i++)
                ans+=m.element[0][i]*a[i]%10000000007;
            printf("%lld\n",ans);
        }
    }
    return 0;

}