package main import ( "bufio" "fmt" "os" ) func main() { N := readLine() M := readLine() //fmt.Println(pow(N, M)) n := []rune(N) m := []rune(M) var n1, m1 int for _, v := range n { n1 = (n1*10+(int(v)-int('0')))%MOD } for _, v := range m { m1 = (m1*10+(int(v)-int('0')))%(MOD-1) } //fmt.Println(n1, m1) fmt.Println(pow(n1, m1)) } // 繰り返し二乗法 // http://judge.u-aizu.ac.jp/onlinejudge/commentary.jsp?id=NTL_1_B // O(log(2)n) const MOD = 129402307 func pow(x, n int) int { var res int if n == 0{ return 1 } if x == 0{ return 0 } res = pow(x, n/2) res = res*res%MOD if n%2==1{ res = res*x%MOD } return res } /////////////////////////////////////////////////// var rdr = bufio.NewReaderSize(os.Stdin, 1000000) func readLine() string { buf := make([]byte, 0) for { l, p, e := rdr.ReadLine() if e != nil { panic(e) } buf = append(buf, l...) if !p { break } } return string(buf) }