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

public class Main {

	private static final String INPUT_FILE_PATH = "lgput.in";
	private static final String OUTPUT_FILE_PATH = "lgput.out";
	
	protected static final int PRIME = 1999999973;

	public static void main(String[] args) throws IOException {
		Scanner in = new Scanner(new FileReader(INPUT_FILE_PATH));
		PrintWriter out = new PrintWriter(OUTPUT_FILE_PATH);
		long n = in.nextLong();
		int p = in.nextInt();
		out.println(MathUtils.moduloPow(n, p));
		in.close();
		out.close();
	}

	static class MathUtils {
		
		static long moduloPow(long base, int exp) {
			long currRes = 1;
			switch (exp % 2) {
			case 0:
				currRes = (exp == 0) ? 1 : moduloPow((base * base) % PRIME, exp / 2);
				break;
			case 1:
				currRes = base * moduloPow(base, --exp);
				break;
			}
			return currRes % PRIME;
		}
		
	}

}