Lũy thừa nhị phân

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.

Giải thích

Binary Exponentiation (hay lũy thừa nhị phân) là kỹ thuật tính lũy thừa với độ phức tạp O(log n), nhanh hơn nhiều so với cách tính thông thường O(n).

Ý tưởng chính:

• a^b = a^(b/2) × a^(b/2) nếu b chẵn
• a^b = a^(b/2) × a^(b/2) × a nếu b lẻ

Input Format

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

Constraints

Phải sử dụng thuật toán lũy thừa nhị phân để tránh tràn số.

Output Format

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

Sample Input 0

2 3

Sample Output 0

8