// Arup Guha
// 9/3/2013
// Solution to 2013 UCF Locals Problem: Goldrush, follows Matt Fontaine's approach to calculating C(k, k/2) via factorials.
import java.util.*;
import java.io.*;
import java.math.*;

public class goldrush {

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

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

		// Fill in factorials first - we will use these for look up.
		fact = new long[SIZE];
		fact[0] = 1;
		for (int i=1; i<SIZE; i++)
			fact[i] = (i*fact[i-1])%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--;

			// We need to look at n choose ceiling(k/2)...
			long[] nFact = modVal(k);
			long[] kLow = modVal(k/2L);
			long[] kHigh = modVal(k/2L+1L);

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

			// 1000003 is a factor, since there are more copies on top than bottom.
			else if (nFact[0] > kLow[0]+kHigh[0])
				System.out.println("0");

			// Being lazy and utilizing BigInteger here...
			else {
				long numerator =   nFact[1];
				long denominator = (kLow[1]*kHigh[1])%MODP;
				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();
	}

	// ret[0] = # times MODP is a factor of n!, ret[1] = (rest of n!) mod MODP.
	public static long[] modVal(long n) {

		// Base case.
		if (n < MODP) {
			long[] ans = new long[2];
			ans[0] = 0;
			ans[1] = fact[(int)n];
			return ans;
		}

		// Recursive case - solve for n/div and then add/mult in contribution on this level to both counts.
		long[] ans = modVal(n/MODP);
		ans[0] += (n/MODP);
		ans[1] = (ans[1]*fact[(int)(n%MODP)])%MODP;
		return ans;
	}
}