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.
A single line with three integers: r n m.
A single integer: the series total, modulo m.
Example 1
Input
2 3 100
Expected
15
Explanation
1 + 2 + 4 + 8 = 15, and 15 mod 100 is 15.
Example 2
Input
3 0 7
Expected
1
Explanation
With n = 0 the sum is just r^0 = 1, and 1 mod 7 is 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →