学步园

import java.math.BigInteger;
import java.util.Scanner;

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
   
	   Scanner scanner=new Scanner(System.in);
	   int t=scanner.nextInt();
	   int time;
	   while(t--!=0)
	   {
		   time=1;
		   BigInteger bigInteger1=BigInteger.ZERO;
		   int x=scanner.nextInt();
		   int y=scanner.nextInt();
		   for(;time<=x;time++)
		   {
			   BigInteger bigInteger3=BigInteger.valueOf(time);
			   bigInteger3=bigInteger3.modPow(BigInteger.valueOf(y), BigInteger.valueOf(10003));
			   bigInteger1=bigInteger1.add(bigInteger3);
			   bigInteger1.mod(BigInteger.valueOf(10003));
		   }
		   System.out.println(bigInteger1.mod(BigInteger.valueOf(10003)));
	   }
	}

}