Bạn là kỹ sư truyền dẫn của Viettel, phụ trách hệ thống quản lý hàng nghìn trạm phát sóng (BTS) trải dài từ Hà Giang đến Cà Mau. Để bảo mật vị trí địa lý của các trạm chiến lược, bộ phận an toàn thông tin thiết kế một hàm băm: mỗi trạm được gán một mã số cơ sở a và một chữ ký điện tử b. Mã định danh cuối cùng của trạm chính là giá trị với .
Vì số lượng trạm rất lớn và số mũ b có thể lên tới một tỷ, bạn cần viết chương trình tính thật nhanh và chính xác.
Hai số nguyên trên một dòng, cách nhau bởi dấu cách:
a là mã số cơ sở của trạm ().b là số mũ chữ ký ().In ra một số nguyên duy nhất: giá trị .
Ví dụ 1:
Input:
3 5
Output:
243
Giải thích: Ta tính . Vì 243 đã nhỏ hơn nên kết quả chính là 243. Phương pháp nhân bình phương sẽ tính như sau: , , , cuối cùng lấy .
Ví dụ 2:
Input:
2 30
Output:
73741817
Giải thích: . Vì giá trị này vượt quá , ta lấy phần dư: .