Cho hai số nguyên dương ~a~ và ~b~.

Hãy tính giá trị:

~a^b mod (10^9 + 7)~

Kiến thức cần sử dụng trong bài toán là thuật toán Binary Exponentiation (Lũy thừa nhị phân).

Dữ liệu vào

• Dòng duy nhất chứa hai số nguyên dương ~a~ và ~b~.

Ràng buộc

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

Kết quả

In ra giá trị của:

~a^b mod (10^9 + 7)~.

Ví dụ

Dữ liệu vào

2 10

Kết quả

1024

Giải thích

Ta có:

~2^10 = 1024~

và:

~1024 mod (10^9 + 7) = 1024~

nên kết quả là ~1024~.