Elementary Number Theory - Power

時間制限 : 1 sec, メモリ制限 : 131072 KB
英語版はこちら

べき乗

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

入出力例


入力例 2

5 8

出力例 2

390625

Note

      解説