Fibonacci Modulo
EasyMathDynamic Programming
Description
Return the n-th Fibonacci number modulo m, where F(0)=0, F(1)=1, F(k)=F(k-1)+F(k-2).
Examples
Input:
n = 10, m = 1000Output:
55Explanation:
F(10) = 55, and 55 mod 1000 = 55.
Input:
n = 0, m = 7Output:
0Explanation:
F(0) is defined as 0, so the result modulo 7 is 0.
Input:
n = 100, m = 1000000007Output:
687995182Explanation:
F(100) is large; computed modulo 10^9+7 it equals 687995182.
Constraints
- •
0 ≤ n ≤ 10⁸ - •
1 ≤ m ≤ 10⁹