// Arup Guha
// Solution to UF Contest Question: Lock Code
// 1/30/2010
import java.util.*;

public class lock {
	
	public static void main(String[] args) {
		
		Scanner stdin = new Scanner(System.in);
		
		// Get both numbers.
		long base = stdin.nextLong();
		long exp = stdin.nextLong();
		
		// Output the answer (mod 1000000).
		while (base != 0 || exp != 0) {
			
			// Solve the problem and pad with zeroes if necessary.
			long ans = modExp(base,exp,1000000);
			String properformat = format(ans);
			
			System.out.println(properformat);
			base = stdin.nextLong();
			exp = stdin.nextLong();
		}
		
	}
	
	// This is the standard fast exponentiation algorithm.
	// You can just call modPow in BigInteger also...
	public static long modExp(long base, long exp, long mod) {
		
		// Base case.
		if (exp == 0)
			return 1;
			
		// For even exponents, this code is fast because of this case.
		else if (exp%2 == 0) {
			
			// Find the square root and then square it to get the answer.
			long sqrt = modExp(base, exp/2,mod);
			return sqrt*sqrt%mod;
		}
		
		// Standard break-down of the power problem...
		else
			return base*modExp(base,exp-1,mod)%mod;
	}
	
	// Assumes ans is 6 or fewer digits long and prepends it with 0s to return an
	// equivalent string of length 6.
	public static String format(long ans) {
		
		// Tricky case.
		if (ans == 0)
			return "000000";
			
		// Get the number of digits in ans.
		int numdigits = 0;
		long tmp = ans;
		while (tmp > 0) {
			tmp /= 10;
			numdigits++;
		}
		
		// Pad by the appropriate number of zeroes.
		String retval = "";
		for (int i=0; i<6-numdigits; i++)
			retval = retval + "0";
			
		// Return the answer.
		return retval + ans;
	}
}