Gọi ~r(x,m)~ là số dư của phép chia số ~x~ cho số ~m~.

Ta định nghĩa dãy vô hạn ~A~ như sau:

• ~A_1 = x~
• ~A_{n+1}=r(A^2_n,m)~ với ~(n > 1)~

Yêu cầu: Tính tổng của ~n~ số đầu tiên trong dãy ~A~.

Dữ liệu vào:

• Dòng duy nhất chứa ba số nguyên: ~n,x,m~ mỗi số cách nhau bởi một dấu cách ~(1≤n≤10^{10}, 0≤x≤m≤10^5)~.

Kết quả: Một số duy nhất cho biết kết quả bài toán.

Giới hạn:

• 20% số điểm: ~n≤10^5~;
• 30% số điểm: ~m≤1000~.

Ví dụ

Input:

10 2 11 

Output:

48