public static void main(String[] args) throws FileNotFoundException {
        long MODULAR = 1000000007;
        System.setIn(new FileInputStream("in.small"));
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        while (t-- > 0) {
            int n = in.nextInt();
            int m = in.nextInt();
            long[] ways = new long[m + 5];
            long[] powWays = new long[m + 5];
            long[] firstSplit = new long[m + 5];
            ways[1] = 1;
            ways[2] = 2;
            ways[3] = 4;
            ways[4] = 8;
            firstSplit[1] = 1;

            for (int i = 5; i <= m; i++)
                for (int j = 1; j <= 4; j++)
                    ways[i] += ways[i - j] % MODULAR;

            for (int i = 1; i <= m; i++) {
                long k = 1;
                for (int j = 1; j <= n; j++) {
                    k = (k * ways[i]) % MODULAR;
                }
                powWays[i] = k;
            }

            for (int i = 2; i <= m; i++) {
                long sum = 0;
                for (int j = 1; j < i; j++) {
                    sum = (sum + firstSplit[j] * powWays[i - j]) % MODULAR;
                }
                firstSplit[i] = ((powWays[i] - sum) % MODULAR + MODULAR) % MODULAR;
            }
            System.out.println(firstSplit[m] % MODULAR);
        }
    }