Cấp số nhân là một dãy số thỏa mãn điều kiện tỷ số giữa \(2\) phần tử liên tiếp là hằng số. Xét dãy cấp số nhân \(1,x,x^2,x^3...,x^n\) .

Yêu cầu

• Cho \(2\) số nguyên \(x\) và \(n\). Tính tổng tất cả các phần tử trong cấp số nhân đã cho. Vì kết quả có thể rất lớn nên chỉ đưa ra số dư trong phép chia cho \(m\).

Dữ liệu vào

• Một dòng chứa \(3\) số nguyên dương \(x,n,m\) \((x \le 100, n \le 10^{18}, m \le 10^7)\)

Dữ liệu ra

Một số nguyên là kết quả của bài toán.

Input 1

2 6 1000

Output 1

127