using System; using System.Collections; using System.Collections.Generic; using System.Collections.Specialized; using System.Text; using System.Text.RegularExpressions; using System.Linq; using System.IO; class Program { static void Main(string[]args) { Magatro alice = new Magatro(); alice.Scan(); alice.Solve(); } } public class Scanner { private StreamReader Sr; private string[] S; private int Index; private const char Separator = ' '; public Scanner() { Index = 0; S = new string[0]; Sr = new StreamReader(Console.OpenStandardInput()); } private string[] Line() { return Sr.ReadLine().Split(Separator); } public string Next() { string result; if (Index >= S.Length) { S = Line(); Index = 0; } result = S[Index]; Index++; return result; } public int NextInt() { return int.Parse(Next()); } public double NextDouble() { return double.Parse(Next()); } public long NextLong() { return long.Parse(Next()); } public string[] StringArray(int index = 0) { Next(); Index = S.Length; return S.Skip(index).ToArray(); } public int[] IntArray(int index = 0) { return StringArray(index).Select(int.Parse).ToArray(); } public long[] LongArray(int index = 0) { return StringArray(index).Select(long.Parse).ToArray(); } public bool EndOfStream { get { return Sr.EndOfStream; } } } public class Magatro { private string N, M; const int Mod = 129402307; public void Scan() { Scanner sc=new Scanner(); N = sc.Next(); M = sc.Next(); } public void Solve() { long lN = ToLong(N, Mod); long lM = ToLong(M, Mod - 1); Console.WriteLine(MyPow(lN, lM, Mod)); } private long MyPow(long x,long y,long mod) { long result = 1; while (y > 0) { if (y % 2 == 0) { x = (x * x) % mod; y /= 2; } else { result = (result * x) % mod; y--; } } return result; } private long ToLong(string s,long mod) { long temp = 0; for(int i = 0; i < s.Length; i++) { temp *= 10; temp += int.Parse(s[i].ToString()); temp %= mod; } return temp; } }