package yukicoder; import java.math.BigInteger; import java.util.Scanner; public class Main{ public static void main(String[] args)throws Exception{ new Main().solve(); } final long mod=129402307; void solve(){ Scanner sc=new Scanner(System.in); BigInteger n=new BigInteger(sc.next()); BigInteger m=new BigInteger(sc.next()); BigInteger ans=pow(n,m,mod); System.out.println(ans); //n^m mod p を求める。 } /** * A^N mod p * * 1.フェルマーの小定理を用いてNをp-1以下にする * 2.繰り返し二乗法 * */ BigInteger pow(BigInteger A,BigInteger n,long p){ BigInteger ans=BigInteger.ONE; n=n.remainder(BigInteger.valueOf(p-1)); while(n.compareTo(BigInteger.ONE)>=0){ if(n.remainder(BigInteger.valueOf(2)).compareTo(BigInteger.valueOf(0))==0){ A=A.multiply(A); A=A.remainder(BigInteger.valueOf(p)); n=n.divide(BigInteger.valueOf(2)); }else if(n.remainder(BigInteger.valueOf(2)).compareTo(BigInteger.valueOf(1))==0){ ans=ans.multiply(A); ans=ans.remainder(BigInteger.valueOf(p)); n=n.subtract(BigInteger.ONE); } } return ans; } }