using System;
using System.Numerics;

namespace No251{
    public class Program{
        public static void Main(string[] args){
            var N = BigInteger.Parse(Console.ReadLine());
            var M = BigInteger.Parse(Console.ReadLine());
            var P = 129402307;
            Console.WriteLine(BigInteger.ModPow(N % P, M % (P - 1), P));
        }
    }
}