Cho 2 số nguyên không âm a và b. Hãy tính a^b%(10^9+7). Kiến thức bạn cần sử dụng là Binary Exponentiation.

Input Format

2 số nguyên dương a, b.(1≤a,b≤10^9)

Constraints

.

Output Format

In ra kết quả của bài toán.

Ví dụ:

Dữ liệu vào

2 3

Dữ liệu ra

8