時間制限 : sec, メモリ制限 : KB
English / Japanese  

べき乗

2つの整数 m, nについて、mnを1,000,000,007で割った余りを求めてください。

入力

m n

2つの整数 m, n が1つの空白区切りで1行に与えられます。

出力

mnを1,000,000,007で割った余りを1行に出力します。

制約

  • 1 ≤ m ≤ 100
  • 1 ≤ n ≤ 109

入出力例


入力例 1

2 3

出力例 1

8

入力例 2

5 8

出力例 2

390625