PreviousNext
Coding/Bits and math

Geometric series modulo

Write codeHard30 min

Your task

Compute S = (1 + a + a^2 + ... + a^(b-1)) mod m, the sum of a geometric series with b terms, where 0 <= a, 0 <= b <= 10^18, and 1 <= m <= 10^9. Use a divide-and-conquer recurrence so it runs in O(log b) modular operations (do NOT loop b times). If b == 0 the sum is 0.

Examples

geo_series_mod(a: int, b: int, m: int) -> int
Example 1
Inputgeo_series_mod(2, 4, 1000000007)
Output15