Bài 13.1. Lũy Thừa Của Những Con Số - [Độ khó: Dễ]

Trong thế giới ảo của "Kẻ Tạo Phép Thuật", một phép thuật cường hóa được định nghĩa bởi công thức x^n. Tuy nhiên, để tránh năng lượng bị tràn ngập vũ trụ, kết quả của phép thuật phải được tính theo một modulo nhất định, thường là 10^9 + 7. Bạn được giao nhiệm vụ xây dựng một hệ thống tính toán phép thuật này một cách hiệu quả nhất, đặc biệt khi n có thể rất lớn. Hãy sử dụng kỹ thuật đệ quy để tính x^n một cách nhanh chóng.

INPUT FORMAT

Dòng duy nhất chứa hai số nguyên x và n.

• 1 <= x <= 10^9
• 0 <= n <= 10^5

OUTPUT FORMAT

Một số nguyên duy nhất là giá trị của (x^n) % (10^9 + 7).

Ví dụ:

Input:

2 10

Output:

1024

Giải thích:

• 2^10 = 1024. 1024 % (10^9 + 7) = 1024.
• Để tính x^n bằng đệ quy nhanh, ta có thể dùng công thức:
  • Nếu n = 0, x^0 = 1.
  • Nếu n chẵn, x^n = (x^(n/2))^2.
  • Nếu n lẻ, x^n = x * (x^(n/2))^2.
• Ví dụ với x=2, n=10:
  • pow(2, 10): n chẵn. return pow(2, 5) * pow(2, 5)
  • pow(2, 5): n lẻ. return 2 * pow(2, 2) * pow(2, 2)
  • pow(2, 2): n chẵn. return pow(2, 1) * pow(2, 1)
  • pow(2, 1): n lẻ. return 2 * pow(2, 0) * pow(2, 0)
  • pow(2, 0): n bằng 0. return 1
• Kết hợp lại các kết quả từ dưới lên sẽ cho ra 1024.