/*
Problem: CNTDSETS
Author: Mugurel Ionut Andreica (mugurelionut)
 
Description of the solution:
 
In order for a set of points to have diameter D under the
given distance (which is the L-infinity distance) they
must all be located inside an N-dimensional cube of
side length D. Moreover, we must have at least one pair of
points located on opposite sides of the cube (the points from the
pair are located at distance exactly D and they ensure that
the diameter of the set of points is exactly D and not less
than D).
In order to make sure that we count only sets of points which are
not equivalent under translation we will want to count sets
of points which are located inside the N-dimensional cube
(0,...,0)-(D,...,D) and have at least one point in each dimension
with coordinate 0 (i.e. they have at least one
point with the i^th coordinate equal to 0; for each 1 <= i <= N). Note
that any set which has at least one dimension i where all of its points
have >0 coordinates can be translated into a set which has at least
one point with the i^th coordinate equal to 0.
With these observations we realize that we need to count the sets
of points located inside the N-dimensional cube of side length D such
that: they have at least one point with coordinate 0 in each of the N
dimensions and they have at least one point with coordinate D in at
least one of the N dimensions.
 
We will split the cube's volume into zones according to the information
that we are interested in. A zone can be described as an (N+1)-bit
number: Z(0), Z(1), ..., Z(N).
- if Z(i)=1 this means that all the points in the zone have
coordinate 0 in dimension i+1 (0 <= i <= N-1); if Z(i)=0 then
none of the points in the zone has coordinate 0 in dimension i+1.
- if Z(N)=1 this means that the zone contains at least one point with
coordinate D in at least one of the N dimensions; otherwise Z(N)=0.
We should notice that the union of the 2^(N+1) zones covers the whole
N-dimensional cube. Let's consider a point (x(1),...,x(N)). This
point belongs to exactly one zone Z corresponding to those dimensions
i where x(i)=0 (and, if it has coordinate D in any of the dimensions,
the zone Z will have Z(N)=1).
 
We will compute CNT(Z) = the number of points located in the cube's zone
described by the binary configuration Z.
 
Let's consider first the case where Z(N)=0. Let X be the number of bits
of Z (from 0 to N-1) which are equal to 0. Each of these bits represents
a dimension in which there are no points with coordinate 0. Moreover,
there are no points with coordinate D in any dimension (because Z(N)=0).
Thus, CNT(Z)=(D-1)^X.
If Z(N)=1 then we must have at least one dimension with a point having
coordinate D in that dimension. Obviously, this dimension must be one of
the X dimensions mentioned earlier. The total number of points having
coordinates from 1 to D in X dimensions is D^X. The total number of
points having coordinates from 1 to D-1 in X dimensions is (D-1)^X
(these points do not have any coordinate equal to D in any of the X
dimensions). Thus, CNT(Z)=D^X - (D-1)^X.
 
Finally, when N and D both become large we cannot store CNT(Z) exactly
(because they become very large numbers). However, when
computing the final result, all the numbers CNT(Z) will be used as exponents
(we will make use of numbers of the form 2^CNT(Z)). Since 10^9 + 7 is a
prime number we know that 2^(10^9 + 6) = 1. Thus, it is enough to store
all the numbers CNT(Z) modulo (10^9 + 6).
The first part takes O(N * 2^(N+1)) time.
 
For the second step there are two possible solutions.
The first solution uses a dynamic programming algorithm. We will
interpret the binary configurations Z as both configurations and numbers
(from 0 to 2^(N+1) - 1).
 
We will compute DPCNT(Z,W) = the number of sets of points formed only
out of points from configurations Z'<=Z and such that the union of the
configurations used so far is W (i.e. their bitwise OR is equal to W).
 
We have DPCNT(0,0)=CNT(0) and DPCNT(0,W>0)=0.
 
For 1<=Z<=2^(N+1) - 1:
1) we initialize DPCNT(Z,W)=DPCNT(Z-1,W) (this corresponds to the
case in which no point from the zone Z is selected)
2) we will consider all the configurations W such that DPCNT(Z-1,W)>0
and we will set: DPCNT(Z, W OR Z) += DPCNT(Z-1,W) * (2^CNT(Z) - 1).
 
The term 2^CNT(Z) - 1 is the number of ways of choosing at least one
point from the zone Z. All the arithmetic operations (multiplication,
addition, raising to a given power) are performed modulo (10^9 + 7).
 
The answer is equal to DPCNT(Z=2^(N+1) - 1, W=2^(N+1) - 1)
(the final W must be equal to 2^(N+1) - 1 in order to be sure that
we have at least one point with coordinate 0 in each dimension and
at least one point with coordinate D in any dimension).
 
The time complexity of the dynamic programming algorithm is O(2^(N+1) *
2^(N+1)) = O(2^(2*N+2)) = O(4^(N+1))).
 
In terms of memory we always need only two rows of the DPCNT table
(DPCNT(Z,*) and DPCNT(Z-1,*)), so the memory used is of the
order O(2^(N+1)). With some attention only one row is needed (see
the implementation).
 
A second solution for the second step makes use of the inclusion-
exclusion principle. We will define for each binary configuration Z
a value WPROD(Z) = Product of (2^CNT(Z')), where Z' is included in
(or equal to) Z. All the values WPROD[Z] can be computed in
O(3^(N+1)) time.
 
WPROD(Z) denotes the total number of ways of choosing points from
the N-dimensional cube of side length D such that the union of the
zones of those points (i.e. their bitwise OR) is included in (or
equal to) Z.
 
With the WPROD(*) values computed, the answer is simply based on
using the inclusion-exclusion principle:
ANSWER = Sum(0 <= Z <= 2^(N+1) - 1) ((-1)^X(Z)) * WPROD(Z).
 
X(Z) denotes the number of 0 bits in Z (the bits are numbered from 0 to N).
 
The inclusion-exclusion solution can be turned into a polynomial-time
solution.
 
First of all, we should notice that CNT(Z) is the same for all the
binary configurations Z having the same number of 0 bits and the
same value of Z(N). The same hold for WPROD(Z).
 
This means that we do not need to consider 2^(N+1) zones. Instead,
we can consider only 2*(N+1) types of zones (each type has X 0 bits
among the first N bits (X=0,...,N) and has either Z(N)=0 or Z(N)=1).
 
For each type we will compute CNTX = the corresponding CNT(Z) value.
We define CNTX(0,X) and CNTX(1,X) (according to the Z(N) bit and the value
of X). CNTX(0,X)=(D-1)^X and CNTX(1,X)=D^X - (D-1)^X.
Then we will compute WP(0,X) and WP(1,X) (the corresponding WPROD for
each type). For WP(0,X) we need to consider all the possible types
of zones included in this type. We can use a parameter Y=X to N :
there are COMB(N-X,N-Y) zones included in (0,X), each contributing
with a value CNTX(0,Y).
 
WP(1,X) is first initialized to WP(0,X) and then we use a similar
algorithm (we use a parameter Y=X to N and there are COMB(N-X,N-Y)
zones included in (1,X), each contributing with a value CNTX(1,Y)).
In order to use the WP(*,X) values in the inclusion-exclusion
method we need to notice that each type (*,X) occurs COMB(N,X)
times in the inclusion-exclusion equation.
 
The algorithm has a time complexity of O(N^2 + N*log(MOD-1)), where
MOD=1000000007 (log(MOD-1) is the time complexity of an exponentiation).
The solution uses O(N^2) memory for storing all the possible
values of the binomial coefficients.
*/
 
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
 
/* There are 2 methods of counting the number of
points in each zone (1 and 2). Both methods can be
used in conjunction with COUNTING_METHOD 1, 2 and 3.
CNTMASK_GENERATION_METHOD 0 is used in conjunction
with COUNTING_METHOD 4 and means that the
CNTMASK values are not computed anymore (because
they are not needed by COUNTING_METHOD 4). */
#define CNTMASK_GENERATION_METHOD 0
 
/* COUNTING_METHOD 1 uses backtracking for computing
the answer. This method is too slow.
COUNTING_METHOD 2 uses the 4^(N+1) dynamic programming
algorithm.  This method is also too slow.
COUNTING_METHOD 3 uses the 3^(N+1) inclusion-exclusion
algorithm.  This method is still too slow.
COUTING_METHOD 4 uses the polynomial-time inclusion-exclusion
algorithm. This method fits the time limit.
*/
#define COUNTING_METHOD 4
 
#define MOD 1000000007ULL
#define PMOD 1000000006ULL // MOD-1
 
#define SMALL_NMAX 20
 
int N, D, MASKMAX;
unsigned long long tmpans, answer;
 
unsigned long long RaiseToPow(unsigned long long x, unsigned long long y, int mod) {
	if (y == 0)
		return (1 % mod);
	if (y == 1)
		return (x % mod);
	unsigned long long result = RaiseToPow(x, y >> 1, mod);
	result = (result * result) % mod;
	if (y & 1)
		result = (result * x) % mod;
	return result;
}
 
unsigned long long cntmask[1 << (SMALL_NMAX + 1)];
 
// CNTMASK_GENERATION_METHOD 1.
void GeneratePointClasses(int d, int mask) {
	if (d == N) {
		cntmask[mask] += tmpans;
		while (cntmask[mask] >= PMOD)
			cntmask[mask] -= PMOD;
	} else {
		unsigned long long oldtmpans = tmpans;
 
		GeneratePointClasses(d + 1, mask | (1 << d));
 
		if (mask & (1 << N)) {
			tmpans = (tmpans * D) % PMOD;
			GeneratePointClasses(d + 1, mask);
		} else {
			GeneratePointClasses(d + 1, mask | (1 << N));
			tmpans = (tmpans * (D - 1)) % PMOD;
			GeneratePointClasses(d + 1, mask);
		}
	
		tmpans = oldtmpans;
	}
}
 
// CNTMASK_GENERATION_METHOD 2.
void ComputeCntmask() {
	int i, j, mask;
	
	for (mask = 0; mask <= MASKMAX; mask++) {
		for (i = j = 0; i < N; i++)
			if (mask & (1 << i))
				j++;
 
		if (mask & (1 << N)) {
			cntmask[mask] = (RaiseToPow(D, N - j, PMOD) - RaiseToPow(D - 1, N - j, PMOD) + PMOD) % PMOD;
		} else {
			cntmask[mask] = RaiseToPow(D - 1, N - j, PMOD);
		}
	}
}
 
// COUNTING_METHOD 1: Count using backtracking.
int cmask;
unsigned long long tp, cp;
 
void BKT(int mask) {
	if (mask <= MASKMAX) {
		if (cntmask[mask] == 0) {
			BKT(mask + 1);
			return;
		}
 
		unsigned long long oldtmpans = tmpans;
		int oldcmask = cmask;
 
		cmask |= mask;
		cp = (cp + cntmask[mask]) % PMOD;
 
		if (cmask != oldcmask) {
			tmpans = (tmpans * (RaiseToPow(2, cntmask[mask], MOD) + MOD - 1)) % MOD;
	
			if (cmask == MASKMAX) {
				tmpans = (tmpans * RaiseToPow(2, (tp - cp + PMOD) % PMOD, MOD)) % MOD;
				answer = (answer + tmpans) % MOD;
			} else
				BKT(mask + 1);
 
			tmpans = oldtmpans;
			cmask = oldcmask;
			BKT(mask + 1);
		} else {
			tmpans = (tmpans * RaiseToPow(2, cntmask[mask], MOD)) % MOD;
			BKT(mask + 1);
			tmpans = oldtmpans;
		}
 
		cp = (cp - cntmask[mask] + PMOD) % PMOD;
	}
}
 
void CountUsingBKT() {
	int i;
 
	answer = 0;
	tmpans = RaiseToPow(2, cntmask[0], MOD);
	cmask = 0;
	cp = cntmask[0];
	tp = 1;
	for (i = 1; i <= N; i++)
		tp = (tp * (D + 1)) % PMOD;
	BKT(1);
 
	fprintf(stderr, "bkt ans=%llu\n", answer);
}
 
// COUNTING_METHOD 2: Count using 4^(N+1) DP.
unsigned long long dpcnt[1 << (SMALL_NMAX + 1)];
 
void CountUsingDP() {
	int mask, pmask, nmask;
 
	memset(dpcnt, 0, sizeof(dpcnt));
	dpcnt[0] = RaiseToPow(2, cntmask[0], MOD);
 
	for (mask = 1; mask <= MASKMAX; mask++) {
		if (cntmask[mask] == 0)
			continue;
		tmpans = (RaiseToPow(2, cntmask[mask], MOD) - 1 + MOD) % MOD;
	
		for (pmask = MASKMAX; pmask >= 0; pmask--) {
			nmask = pmask | mask;
			dpcnt[nmask] = (dpcnt[nmask] + dpcnt[pmask] * tmpans) % MOD;
		}
	}
 
	answer = dpcnt[MASKMAX];
	fprintf(stderr, "4^(N+1) dp ans= %llu\n", answer);
}
 
// COUNTING_METHOD 3: Count using 3^(N+1) inclusion-exclusion.
unsigned long long w[1 << (SMALL_NMAX + 1)], wprod[1 << (SMALL_NMAX + 1)];
int submask, supermask;
 
void GenSubsets(int d) {
	if (d == N + 1)
		wprod[supermask] = (wprod[supermask] * w[submask]) % MOD;
	else {
		GenSubsets(d + 1);
		
		submask |= (1 << d);
		supermask |= (1 << d);
		GenSubsets(d + 1);
		
		submask ^= (1 << d);
		GenSubsets(d + 1);
 
		supermask ^= (1 << d);
	}
}
 
void CountUsingExpInclusionExclusion() {
	int mask, i, nbits;
	
	for (mask = 0; mask <= MASKMAX; mask++) {
		w[mask] = RaiseToPow(2, cntmask[mask], MOD);
		wprod[mask] = 1;
	}
 
	submask = supermask = 0;
	GenSubsets(0);
	
	answer = 0;
	for (mask = 0; mask <= MASKMAX; mask++) {
		for (i = nbits = 0; i <= N; i++)
			if ((mask & (1 << i)) == 0)
				nbits++;
		if ((nbits & 1) == 0)
			answer = (answer + wprod[mask]) % MOD;
		else
			answer = (answer - wprod[mask] + MOD) % MOD;
	}
 
	fprintf(stderr, "incl-excl 3^(N+1) ans=%llu\n", answer);
}
 
// COUNTING_METHOD 4: Count using polynomial-time inclusion exclusion.
 
#define LARGE_NMAX 1001
unsigned long long CMOD[LARGE_NMAX][LARGE_NMAX], CPMOD[LARGE_NMAX][LARGE_NMAX];
 
void ComputeComb() {
	int i, j;
 
	CMOD[0][0] = CPMOD[0][0] = 1;
	for (i = 1; i < LARGE_NMAX; i++) {
		CMOD[i][0] = CPMOD[i][0] = 1;
		for (j = 1; j <= i; j++) {
			CMOD[i][j] = (CMOD[i - 1][j - 1] + CMOD[i - 1][j]) % MOD;
			CPMOD[i][j] = (CPMOD[i - 1][j - 1] + CPMOD[i - 1][j]) % PMOD;
		}
	}
}
 
unsigned long long CNTX[2][LARGE_NMAX], WP[2][LARGE_NMAX];
 
void CountUsingPolyInclusionExclusion() {
	int X, Y;
	
	for (X = 0; X <= N; X++) {
		CNTX[0][X] = RaiseToPow(D - 1, X, PMOD);
		CNTX[1][X] = (RaiseToPow(D, X, PMOD) - RaiseToPow(D - 1, X, PMOD) + PMOD) % PMOD;
	}
	
	for (X = 0, answer = 0; X <= N; X++) {
		WP[0][X] = CNTX[0][X];
		for (Y = X + 1; Y <= N; Y++)
			WP[0][X] = (WP[0][X] + CNTX[0][Y] * CPMOD[N - X][N - Y]) % PMOD;
 
		WP[1][X] = (WP[0][X] + CNTX[1][X]) % PMOD;
		for (Y = X + 1; Y <= N; Y++)
			WP[1][X] = (WP[1][X] + CNTX[1][Y] * CPMOD[N - X][N - Y]) % PMOD;
 
		WP[0][X] = RaiseToPow(2, WP[0][X], MOD);
		WP[1][X] = RaiseToPow(2, WP[1][X], MOD);
 
		if ((X & 1) == 0) {
			answer = (answer + CMOD[N][X] * WP[1][X]) % MOD;
			answer = (answer - ((CMOD[N][X] * WP[0][X]) % MOD) + MOD) % MOD;
		} else {
			answer = (answer + CMOD[N][X] * WP[0][X]) % MOD;
			answer = (answer - ((CMOD[N][X] * WP[1][X]) % MOD) + MOD) % MOD;
		}
	}
 
	fprintf(stderr, "incl-excl poly ans=%llu\n", answer);
}
 
int main() {
	int tstart = clock(), T;
 
	if (COUNTING_METHOD == 4)
		ComputeComb();
 
	scanf("%d", &T);
	assert(T >= 1 && T <= 10);
	
	while (T--) {
		scanf("%d %d", &N, &D);
		assert(N >= 1 && N <= 1000);
		assert(D >= 1 && D <= 1000000000);
 
		if (CNTMASK_GENERATION_METHOD > 0) {
			MASKMAX = (1 << (N + 1)) - 1;
	
			memset(cntmask, 0, sizeof(cntmask));
			if (CNTMASK_GENERATION_METHOD == 1) {
				tmpans = 1;
				GeneratePointClasses(0, 0);
			} else
				ComputeCntmask();
		}
	
		if (COUNTING_METHOD == 1)
			CountUsingBKT();
		else if (COUNTING_METHOD == 2)
			CountUsingDP();
		else if (COUNTING_METHOD == 3)
			CountUsingExpInclusionExclusion();
		else if (COUNTING_METHOD == 4)
			CountUsingPolyInclusionExclusion();
 
		printf("%llu\n", answer);
	}
 
	fprintf(stderr, "Duration=%.3lf sec\n", (double) (clock() - tstart) / CLOCKS_PER_SEC);
	return 0;
}