Lũy thừa nhị phân.

Bối cảnh

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.

Yêu cầu

Input

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

Output

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

Ràng buộc

Đề gốc không nêu ràng buộc riêng.

Ví dụ 1

Input

12 4

Output

4 12

Thông tin học tập

• Buổi: B08
• Concepts: binary exponentiation, modulo, loops, functions
• Giới hạn kiến thức: B01-B08
• Time limit: 2 seconds
• Memory limit: 20 MB
• Point: 10