Problem Description

Define f(n) as the number of ways to perform n in format of the sum of some positive integers. For instance, when n=4, we have
  4=1+1+1+1
  4=1+1+2
  4=1+2+1
  4=2+1+1
  4=1+3
  4=2+2
  4=3+1
  4=4
totally 8 ways. Actually, we will have f(n)=2^(n-1) after observations.
Given a pair of integers n and k, your task is to figure out how many times that the integer k occurs in such 2^(n-1) ways. In the example above, number 1 occurs for 12 times, while number 4 only occurs once.

 

Input

The first line contains a single integer T(1≤T≤10000), indicating the number of test cases.
Each test case contains two integers n and k(1≤n,k≤10⁹).

 

Output

Output the required answer modulo 10⁹+7 for each test case, one per line.

 

Sample Input

 

Sample Output

 

Source

 

Recommend

liuyiding

 

列出了 n=5 时 5,4,3,2,1 出现的次数为 1 2 5 12 28
f[n+1]=3*f[n]-f[n-1]-f[n-2]-..f[1]
f[n]=3*f[n-1]-f[n-2]-..f[1]
==> f[n+1]=4*f[n]-4*f[n-1]

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int mod=;

struct Matrix{

    long long arr[][];

};

Matrix init,unit;

int n,k;

long long num[][]={{,-},{,}};

void Init(){

    for(int i=;i<;i++)

        for(int j=;j<;j++){

            init.arr[i][j]=num[i][j];

            unit.arr[i][j]=(i==j)?:;

        }

}

Matrix Mul(Matrix a,Matrix b){

    Matrix c;

    for(int i=;i<;i++)

        for(int j=;j<;j++){

            c.arr[i][j]=;

            for(int k=;k<;k++)

                c.arr[i][j]=(c.arr[i][j]%mod+a.arr[i][k]*b.arr[k][j]%mod+mod)%mod;

            c.arr[i][j]%=mod;

        }

    return c;

}

Matrix Pow(Matrix a,Matrix b,int k){

    while(k){

        if(k&){

            b=Mul(a,b);

        }

        a=Mul(a,a);

        k>>=;

    }

    return b;

}

int main(){

    //freopen("input.txt","r",stdin);

    int t;

    scanf("%d",&t);

    while(t--){

        scanf("%d%d",&n,&k);

        Init();

        if(k>n){

            printf("0\n");

            continue;

        }

        int tmp=n-k+;

        if(tmp==){

            printf("1\n");

            continue;

        }

        if(tmp==){

            printf("2\n");

            continue;

        }

        if(tmp==){

            printf("5\n");

            continue;

        }

        Matrix res=Pow(init,unit,tmp-);

        //long long ans=((res.arr[0][0]%mod*5)%mod+(res.arr[0][1]%mod*2)%mod)%mod;

        long long ans=(res.arr[][]*+res.arr[][]*)%mod;

        cout<<ans<<endl;

    }

    return ;

}