Description
Return F(n) mod m using the fast-doubling identities, where F(0)=0, F(1)=1. n can be very large (up to 10^18).
Examples
Input:
n = 0, m = 7Output:
0Explanation:
By definition F(0) = 0 and 0 mod 7 equals 0.
Input:
n = 1000000000000000000, m = 1000000007Output:
209783453Explanation:
Fast-doubling Fibonacci mod 10^9+7 at n = 10^18 yields 209783453.
Input:
n = 10, m = 1000000007Output:
55Explanation:
F(10) equals 55 and 55 mod 10^9+7 is 55.
Constraints
- •
0 ≤ n ≤ 10¹⁸ - •
1 ≤ m ≤ 10⁹