/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include <iostream>
#include <stdio.h>

using namespace std;

const int M = 1000000007;
const int maxn = 1000;

long long T[maxn + 1][maxn + 1];
long long B[maxn + 1], G[maxn + 1];

void init()
{
	T[1][0] = 1;
	for (int j = 1; j <= maxn; j++)
	{
		T[1][j] = T[1][j - 1];
		if (j >= 2) T[1][j] += T[1][j - 2];
		if (j >= 3) T[1][j] += T[1][j - 3];
		if (j >= 4) T[1][j] += T[1][j - 4];
		T[1][j] %= M ;
	}
	for (int i = 2; i <= maxn; i++)
		for (int j = 1; j <= maxn; j++) 
		{
			T[i][j] = T[i - 1][j] * T[1][j];
			T[i][j] %= M ;
		}
}

int main()
{
	init();	
	int cs, n, m;
	cin >> cs ;
	while (cs--)
	{
		cin >> n >> m;
		B[1] = 0;
		G[1] = 1;
		for (int j = 2; j <= m; j++)
		{
			B[j] = 0;
			for (int k = 1; k < j; k++)
			{
				B[j] += T[n][j - k] * G[k];
				B[j] %= M ;
			}
			G[j] = (T[n][j] + M - B[j]) % M ;
		}
		cout << G[m] << endl;
	}	
}

import java.util.*;

public class Solution {
	int md=1000000007;
	int[][] ways = new int[1001][1001];
	int[][] waysRestrict = new int[1001][1001];
	public Solution(){
		for(int[] w : ways) Arrays.fill(w, -1);
		for(int[] w : waysRestrict) Arrays.fill(w, -1);
	}
	public int solve(int n, int m)
	{
		if (ways[n][m] != -1) return ways[n][m];
		long ans;
		if (m==1) ans = 1;
		else if (n==1){
			if (m<=4) {
				ans = 2*solve(1,m-1);
			}
			else {
				ans = solve(1,m-1);
				ans = (ans + solve(1,m-2))%md;
				ans = (ans + solve(1,m-3))%md;
				ans = (ans + solve(1,m-4))%md;
			}
		}
		else{
			ans = 1; int one = solve(1,m);
			for (int i=0; i<n; i++) ans = (ans * one)%md;
		}
		ways[n][m] = (int)ans;
		return ways[n][m];
	}
	public int solveRestrict(int n, int m)
	{
		if (waysRestrict[n][m] != -1) return waysRestrict[n][m];
		long ans;
		if (m==1) ans = 1;

		else {
			ans = solve(n,m);
			for (int i=1; i<m; i++) {
				long a = solve(n,i);
				a = (a*solveRestrict(n,m-i))%md;
				ans -= a;
				if (ans<0) ans+=md;
			}
		}
		waysRestrict[n][m] = (int)ans;
		return waysRestrict[n][m];
	}
	public static void main (String[] args) {
		Solution o = new Solution();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		for (int i=0; i<n; i++) {
			int a, b;
			a = sc.nextInt(); b = sc.nextInt();
			System.out.println(o.solveRestrict(a,b));
		}
		sc.close();
	}
}
 

#!/bin/python3

import os
import sys
import datetime
#
# Complete the legoBlocks function below.
#
def legoBlocks(n, m):
    A = 1000000000+7
    r = [0]*(m+1)
    a = [0]*(m+1)
    print(datetime.datetime.now())

    a[0] = 1
    for j in range(1, m+1):
        a[j] += a[j-1] if j-1>=0 else 0
        a[j] += a[j-2] if j-2>=0 else 0
        a[j] += a[j-3] if j-3>=0 else 0
        a[j] += a[j-4] if j-4>=0 else 0
    print(datetime.datetime.now())    
    for j in range(1, m+1):
        a[j] = a[j] % A
        a[j] = a[j] ** n
        a[j] = a[j] % A
    print(datetime.datetime.now())
    
    r[1] = 1
    for j in range(2, m+1):
        r[j] = a[j]
        for k in range(1, j):
            r[j] -= r[k]*a[j-k]
        r[j] = r[j] % A
    print(datetime.datetime.now())
    return r[m]%A

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(input())

    for t_itr in range(t):
        nm = input().split()

        n = int(nm[0])

        m = int(nm[1])

        result = legoBlocks(n, m)

        fptr.write(str(result) + '\n')

    fptr.close()

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

#define MOD 1000000007
#define MAX 1001

 int N, M,i,j,nPieces = 4;
int pieces[] = {1, 2, 3, 4};
long long RowComb[MAX],ColumnComb[MAX],ColumnCombWithNoHoles[MAX];

void logic()
{
    scanf("%d %d",&N,&M);
    
    memset(RowComb, 0, sizeof(RowComb));
    RowComb[0] = 1;
    for (i = 1; i <= M; i++) {
        for (j = 0; j < nPieces; j++) {
            if (i - pieces[j] >= 0)
                RowComb[i] = (RowComb[i]+RowComb[i - pieces[j]]) % MOD;
        }
    }

    for (i = 1; i <= M; i++) {
        long long res = 1;
        for (j = 1; j <= N; j++) {
            res = (res *RowComb[i]) % MOD;
        }
        ColumnComb[i] = res;
    }
    ColumnCombWithNoHoles[1] = ColumnComb[1];
    for (i = 2; i <= M; i++) {
        ColumnCombWithNoHoles[i] = ColumnComb[i];
        for (j = 1; j < i; j++) {
            ColumnCombWithNoHoles[i] = (MOD + ColumnCombWithNoHoles[i]-(ColumnCombWithNoHoles[j] * ColumnComb[i - j]) % MOD) % MOD;
        }
    }

    printf("%lld\n",ColumnCombWithNoHoles[M]);
    	
}

int main() {
    int T;
	scanf("%d",&T);	
	while(T--) logic();   
    return 0;
}