Tính tổng ~(1 + x^1 + x^2 + x^3 + \ldots + x^N )\%M~.

Input

Dòng duy nhất là ba số nguyên dương ~x, N, M~ thỏa ~1 \le M, N \le 10^{18}~. Giới hạn của ~x~ nằm trong giới hạn số nguyên ~64~ bit

Output

In ra số nguyên duy nhất là kết quả của bài toán.

Samples

Sample Input 1

1 3 100

Sample Output 1

4

Sample Input 2

2 3 100

Sample Output 2

15