ktoj_1085.cpp

#include <cstdio>

using namespace std;

unsigned int win[1000000];

int main(void)
{
	
	int t, n, k;
	unsigned int mod = 1000000007;
	
	scanf("%d", &t);
	for(;t--;) {
		scanf("%d%d", &n, &k);
		
		if(n==1) {
			puts("1");
			continue;
		}
		
		int idx = 0;
		
		unsigned int sum = 1;
		for(int i=0; i<n-1; ++i) {
			win[i] = 0;
		}

		win[n-1] = 1;
		
		for(int i=0; i<k; ++i) {
			win[idx+n] = sum;
			sum = ((sum<<1) + mod - win[idx])%mod;
			++idx;
		}
		
		printf("%d\n", win[k-1]);
	}
	
	
	return 0;
}