べき乗

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

入力

m n

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

出力

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

制約

• 1 ≤ m ≤ 100
• 1 ≤ n ≤ 10⁹

入出力例

入力例 1

2 3

出力例 1

8

入力例 2

5 8

出力例 2

390625

---