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\).

Input

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

Output

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

Example

2 6 1000 

127