Lũy thừa nhanh theo chia đôi

Bối cảnh

Một mô-đun mã hóa cần tính a^n với n rất lớn. Cách nhân a lặp lại n lần không còn phù hợp: với n có thể lên tới 10^18, recursion tuyến tính vừa quá chậm vừa tạo call stack quá sâu. Tuy nhiên, lũy thừa có cấu trúc chia đôi: nếu n chẵn thì a^n = (a^(n/2))²; nếu n lẻ thì chỉ cần nhân thêm một a. Kết quả được lấy modulo 1 000 000 007 để luôn nằm trong phạm vi số nguyên 64-bit.

Bài toán nâng từ định nghĩa recursion tuyến tính ở phiên bản cũ lên tư duy divide-and-conquer cơ bản. Người học phải nhận ra rằng cùng một kết quả a^(n/2) không được gọi hai lần độc lập, nếu không số lời gọi sẽ tăng mạnh. Mỗi tầng chỉ nên gọi một lần cho n/2, lưu kết quả half, bình phương nó rồi xử lý bit lẻ của n. Đây là mẫu kinh điển trong Olympic/ICPC cho bài toán số học.

Yêu cầu

1. Đọc a và n.
2. Chuẩn hóa a theo modulo 1 000 000 007.
3. Viết hàm đệ quy lũy thừa nhanh.
4. Mỗi tầng chỉ gọi đệ quy một lần với n/2.
5. In a^n mod 1 000 000 007.

Yêu cầu tổ chức code

Bắt buộc dùng recursion chia đôi; không dùng pow.

Online Judge chấm output. Giảng viên có thể review source code để xác nhận học viên dùng đúng recursion và không vượt prerequisite.

Input

Một dòng gồm hai số nguyên a n.

Output

Một số nguyên trong [0, 1 000 000 006].

Ràng buộc

-10^9 ≤ a ≤ 10^9, 0 ≤ n ≤ 10^18.

Ví dụ 1

Input

2 10

Output

1024

Giải thích

Với 2^10, hàm không đi theo 10 tầng. Nó chia số mũ: 10→5→2→1→0. Từ base case 1, tầng n=1 tạo 2; n=2 bình phương thành 4; n=5 lấy 4²×2 = 32; n=10 bình phương 32 thành 1024. Vì 1024 nhỏ hơn modulo nên output vẫn là 1024.

Ví dụ 2

Input

5 0

Output

1

Giải thích

Khi n=0, base case trả 1 ngay mà không phụ thuộc vào a. Điều này đúng với định nghĩa dùng trong chương trình, kể cả khi a bằng 0. Vì không có recursive call nào khác, kết quả modulo vẫn là 1.

Thông tin học tập

• Module: M04
• Buổi: B13
• Loại bài: HOMEWORK
• Độ khó: Medium
• Concepts: recursion, fast exponentiation, divide by two, modulo, logarithmic recursion
• Giới hạn kiến thức: B01-B13
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100