1360. A Geometric Series, Modulo p

Print a * (1 + r + r^2 + ... + r^(n-1)) modulo p. With n = 0 the sum is empty and the answer is 0.

The closed form is a * (r^n - 1) / (r - 1), and it is a trap here. That division needs the modular inverse of r - 1, which does not exist when r - 1 is a multiple of p, and in particular the whole form is meaningless when r = 1. Both cases occur in the tests.

Split the sum instead, which needs no division at all:

S(0) = 0 S(n) = S(n-1) + r^(n-1) when n is odd S(n) = S(n/2) * (1 + r^(n/2)) when n is even

The even case is the useful one. The second half of the series is the first half multiplied through by r^(n/2), so the whole sum is the half sum times 1 + r^(n/2). Each step halves n, so the recursion is O(log n) and each level does one fast exponentiation.

Reduce after every multiplication. Two values below 10^9 multiply to just under 10^18, which fits in a 64-bit integer, but only if nothing is left unreduced.

r = 0 is worth checking by hand: the series is 1 + 0 + 0 + ..., so the answer is a for any n at least 1, using the convention that r^0 is 1.

Constraints - `0 ≤ a, r < 1000000007` - `0 ≤ n ≤ 1000000000000000000` - `2 ≤ p ≤ 1000000007`