Cho dãy số \(a^1, a^2, a^3, \dots, a^n\). Hãy tính tổng \(S = a^1 + a^2 + \cdots + a^n\) theo modulo \(M\), với \(M\) là số nguyên tố.

Định dạng đầu vào

• Một dòng chứa ba số nguyên \(a, n, M\) (\(1 \le a, n \le 10^9\), \(2 \le M \le 10^9\), \(M\) nguyên tố).

Định dạng đầu ra

• Một số nguyên là \(S \bmod M\).

Ví dụ

Input:

3 4 1000000007

Output:

120

Giải thích: \(3^1 + 3^2 + 3^3 + 3^4 = 3 + 9 + 27 + 81 = 120\).

Ràng buộc

• 100% số điểm: \(a, n \le 10^9\), \(M\) nguyên tố.