Để chào mừng ngày thành lập Đoàn, câu lạc bộ Truyền thông của trường THPT X tổ chức một chiến dịch mang tên "Lan tỏa thông điệp xanh". Quy tắc tính điểm sức mạnh của chiến dịch được quy định như sau:
Ban đầu, chiến dịch có một chỉ số cơ sở là .
Chiến dịch sẽ trải qua đợt lan tỏa. Ở mỗi đợt, chỉ số sức mạnh hiện tại sẽ được nhân thêm lần. Sau đợt, chỉ số sức mạnh cuối cùng sẽ là .
Do con số này có thể tăng lên rất nhanh và vượt quá khả năng hiển thị của website trường, ban tổ chức quyết định chỉ lấy phần dư của chỉ số sức mạnh này khi chia cho một mã số may mắn .
Nhiệm vụ của bạn là giúp câu lạc bộ tính toán nhanh chóng giá trị chỉ số sức mạnh cuối cùng này để kịp thời cập nhật lên bảng tin điện tử của trường.
Dữ liệu:
Một dòng duy nhất chứa ba số nguyên dương và ().
Kết quả:
In ra một số nguyên duy nhất là giá trị sức mạnh cuối cùng sau khi lấy phần dư cho ().
Ví dụ:
Dữ liệu:
2 10 1000
Kết quả:
24
Dữ liệu:
3 13 1000000007
Kết quả:
1594323
Giới hạn:
Subtask #1 (20% số điểm): .
Subtask #2 (20% số điểm): .
Subtask #3 (30% số điểm): .
Subtask #4 (30% số điểm): Không có giới hạn bổ sung ().
