2015
09-17

# Partition

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.

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≤109).

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≤109).

2
4 2
5 5

5
1

/*

2013multi第一场c题，递推找规律都行。
打个表就能看出来规律了，递推的过程完全就是高中时候数学某

2013-07-23
*/

#include"iostream"
#include"cstdio"
#include"cstring"
using namespace std;
const int mod=1000000007;

__int64 sp(__int64 a,__int64 b)
{
__int64 ans=1;
while(b)
{
if(b%2)	ans=(ans*a)%mod;
b/=2;
a=(a*a)%mod;
}
return ans%mod;
}
__int64 solve(int x)
{
__int64 ans;
if(x==1)	return 1;
if(x==2)	return 2;
if(x==3)	return 5;
ans=((2*sp(2,x-2))%mod+((x-2)*sp(2,x-3))%mod)%mod;
return ans;
}
int main()
{
int T;
int n,k;
int x;
cin>>T;
while(T--)
{
scanf("%d%d",&n,&k);
if(k>n)	{printf("0\n");continue;}
x=n;
x-=(k-1);
printf("%I64d\n",solve(x));
}
return 0;
}