A committee runs like this. The kick-off meeting, round 0, has start attendees. Every later round i has
T(i) \;=\; \mathrm{extra} \;+\; \mathrm{factor} \cdot \sum_{j=0}^{i-1} T(j)
attendees: a fixed extra, plus factor new people for every attendee of every earlier round.
Write attendees(n, start, extra, factor, mod) returning T(n) \bmod \mathrm{mod}.
Examples
Input: n = 3, start = 1, extra = 1, factor = 1, mod = 10**9 + 7
Output: 8
Explanation: the rounds are 1, 2, 4, 8.
Input: n = 0, start = 5, extra = 1, factor = 2, mod = 1000
Output: 5
Explanation: round 0 is always `start`.
Constraints
0 <= n <= 10**18, so the terms cannot be computed one at a time.0 <= start, extra <= 10**9,0 <= factor <= 10**9,2 <= mod <= 10**9 + 7
Goals
- Turn a recurrence with a sum over all earlier terms into one step of telescoping
- Recognise a geometric closed form and evaluate it with fast exponentiation
- Answer for n far beyond what a term-by-term loop could reach