問題文

正整数 N,MN,M が与えられるので NMN^M をアルファベットの個数で割ったあまりを求めてください。

制約

  • 1N,M1061\leqq N,M \leqq 10^6

  • 入力はすべて整数

入力

NN MM

出力

答えを出力してください。

サンプル

入力1
114 514
出力2
16

Submit


Go (1.21)