A community seed library tracks how many seed packets it holds at the start of each season. Every packet lent out comes back multiplied, older stock is still being returned, and a neighbouring farm donates a fixed batch each season. That gives the rule
seeds(0) = a0
seeds(1) = a1
seeds(n) = p · seeds(n-1) + q · seeds(n-2) + r for n >= 2
Write seeds(a0: int, a1: int, p: int, q: int, r: int, n: int) -> int returning seeds(n) % (10**9 + 7).
seeds(1, 2, 1, 1, 1, 5) # 20 (1, 2, 4, 7, 12, 20)
seeds(0, 1, 2, 0, 3, 4) # 29 (0, 1, 5, 13, 29)
seeds(7, 9, 5, 5, 5, 0) # 7
Constraints: 0 <= a0, a1, p, q, r < 10^9 + 7 and 0 <= n <= 10^18, so looping season by season is far too slow.
The Basics drill raised a matrix to a power. The new part here is the constant term r: a plain 2×2 matrix can't add a constant. Carry an extra 1 in the state vector so the matrix can add r · 1 each step.
Show hint
Use the state [seeds(k), seeds(k-1), 1] and the 3×3 matrix [[p, q, r], [1, 0, 0], [0, 0, 1]], which maps it to [seeds(k+1), seeds(k), 1]. Raise it to the power n - 1 by repeated squaring and apply it to [a1, a0, 1].