Cho hai số nguyên dương ~a~ và ~n~. Tính ~a^n~.

Input

• Gồm một dòng duy nhất ghi hai số nguyên dương ~a~ và ~n~ cách nhau bởi dấu cách.

Giới hạn:

• ~1 ≤ a, n ≤ 10^9~.

Output

• Phần dư của phép tính ~a^n~ chia cho ~10^9 + 7~.

Sample

Input #1

5 7

Output #1

78125

Problem source: Chuyên Sơn La Online Judge