// Arup Guha
// 9/1/2013, finished 9/3/2013
// Solution to 2013 UCF Locals Problem: Goldrush
// Note: This approach is a bit different that the one shown in goldrush.java, which is
//       similar to Matt's (Fontaine) approach. In this one, I take the combination of
//       k choose ceiling(k/2) and cancel one of the factorials on the bottom so that
//       the resulting expression is P(k, k/2)/P(k/2, k/2). Oddly enough, calculating this
//       requires solving the arbitrary subproblem of what P(a, b) is mod a prime, which
//       is a bit harder than solving the problem for k!.

import java.util.*;
import java.io.*;
import java.math.*;

public class goldrush2 {

	final public static int SIZE = 1000003;
	final public static long MODP = 1000003L;
	final public static BigInteger MODPBI = new BigInteger("1000003");
	public static long[] fact = new long[SIZE];
	public static long[] revfact = new long[SIZE];

	public static void main(String[] args) throws Exception {

		// Precompute strings of consecutive integers multiplied together MODP.
		fact[0] = 1; revfact[SIZE-1] = SIZE-1; revfact[0] = 1;
		for (int i=1; i<SIZE; i++) fact[i] = (fact[i-1]*i)%MODP;
		for (int i=SIZE-2; i>=1; i--) revfact[i] = (revfact[i+1]*i)%MODP;

		Scanner stdin = new Scanner(new File("goldrush.in"));
		int numCases = stdin.nextInt();

		// Process each case.
		for (int loop=0; loop<numCases; loop++) {

			long n = stdin.nextLong();
			long k = stdin.nextLong();

			// This is pretty silly, the input should have just forced k to be odd.
			if (k%2L == 0) k--;

			// The key calculation, the number of possible outcomes of a single match is 2 times (k choose (ceiling k/2)).
			// These two products will help us calculate this value, mod p.
			long pTop    = numP(k/2L+2L, k);
			long pBottom = numP(1L, k/2L);

			// Easy case where our base is 0 mod p.
			if (n == 1)
				System.out.println("1");

			// Numerator has more copies of MODP than the denominator so the answer is 0.
			else if (pTop > pBottom)
				System.out.println("0");

			// Work this case out. base = 2*C(k, k/2) (for one round), exponent = n-1 (for # rounds)
			else {
				long numerator = 	remainder(k/2L+2L, k);
				long denominator = remainder(1L, k/2L);
				long factor = (new BigInteger(""+denominator)).modInverse(MODPBI).longValue();
				long base = (numerator*factor*2L)%MODP;
				long exp = n-1L;
				BigInteger baseBI = new BigInteger(""+base);
				BigInteger expBI = new BigInteger(""+exp);
				System.out.println(baseBI.modPow(expBI, MODPBI));
			}
		}

		stdin.close();
	}

	// Returns the number of times MODP appears as a factor in the product high!/(low-1)!.
	public static long numP(long low, long high) {

		long cnt = 0L;
		long div = MODP;

		// We need to divide out MODP, MODP^2, etc.
		// For our value of MODP, we wouldn't continue after the second iteration, but
		// I wanted to write this more generally.
		while (div <= high) {
			long start = (low+div-1)/div;
			long end = high/div;
			cnt += (end-start+1);
			div *= MODP;
		}

		return cnt;
	}

	// Let x = high!/(low-1)! after dividing out all copies of MODP. This calculates x mod MODP.
	public static long remainder(long low, long high) {

		// Simple base case.
		if (low > high) return 1L;

		// Here we are returning the product low*(low+1)*...*high.
		if (high < MODP) {
			long ans = fact[(int)high];
			if (low > 2L)
				ans = (ans*((new BigInteger(""+(fact[(int)(low-1)]))).modInverse(MODPBI).longValue()))%MODP;
			return ans;
		}

		// Multiply all factors from low to the first multiple of MODP and from high down to the last multiple of MODP.
		long ans = (revfact[(int)(low%MODP)]*fact[(int)(high%MODP)])%MODP;

		// Use Wilson's Theorem, (p-1)! = -1 mod p for all primes. If we have
		// an even number of repetitions, our mod value doesn't change. If it's odd
		// we just flip it.
		long numMults = (high-low)/MODP;
		if (numMults%2L == 1L)
			ans = MODP-ans;

		return (ans*remainder( (low+MODP-1)/MODP, high/MODP))%MODP;
	}
}