A signal repeater echoes a pulse whose strength is multiplied by a factor r on each hop. After n hops the total accumulated strength is r^0 + r^1 + ... + r^n. Since n can be large, you must report the total modulo m.
Compute (r^0 + r^1 + ... + r^n) mod m. Use the convention r^0 = 1. The intended approach folds the series in half: the sum of 2t terms equals the sum of the first t terms times (1 + r^t), computed with fast exponentiation.
Input format
A single line with three integers: r n m.
Output format
A single integer: the series total, modulo m.
Constraints
- 0 <= r <= 1000000000
- 0 <= n <= 1000000000
- 1 <= m <= 1000000000