1465. Far Fibonacci
A seed vault doubles in a curious way: the first season holds one crate, the second also one, and from then on each season holds as many crates as the previous two seasons together. Counting seasons from 0, season 0 holds 0 crates, season 1 holds 1 and season n holds F(n) = F(n-1) + F(n-2).
Given a season index n, return F(n) modulo 1000000007 as an integer in the range [0, 1000000006]. The index can be astronomically large, so you cannot iterate season by season; use fast doubling or matrix exponentiation to finish in O(log n) time and O(1) space.
Example 1
- Input:
- n = 0
- Output:
- 0
- Explanation:
Season 0 holds 0 crates by definition.
Example 2
- Input:
- n = 10
- Output:
- 55
- Explanation:
The sequence runs 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, so season 10 holds 55 crates.
Example 3
- Input:
- n = 50
- Output:
- 586268941
- Explanation:
F(50) is 12586269025, and 12586269025 mod 1000000007 equals 586268941.
Constraints
0 ≤ n ≤ 1015
Answer modulo 1000000007. Products of two residues exceed 253, so use BigInt or a split multiplication in JavaScript.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(log n)
- Space
- O(1)