Fibonacci Modulo (Pisano Period)

Given integers n and m, compute F(n) mod m where F(n) is the nth Fibonacci number. The challenge is to handle very large values of n (up to 10^18) efficiently.

Key Insight: Fibonacci numbers modulo m are periodic with period length at most 6m (Pisano period).

Examples

Input: n = 10, m = 3
Output: 1
Explanation: F(10) = 55, 55 mod 3 = 1

Input: n = 1000000000000000000, m = 1000000007
Output: 209783453
Explanation: F(10^18) mod 10^9+7 using Pisano period

Input: n = 5, m = 2
Output: 0
Explanation: F(5) = 5, 5 mod 2 = 1 (but F(5) = 5, so 5 mod 2 = 1)

Input: n = 0, m = 1000
Output: 0
Explanation: F(0) = 0, 0 mod 1000 = 0

Input: n = 1, m = 1000
Output: 1
Explanation: F(1) = 1, 1 mod 1000 = 1

Mathematical Background

The Pisano period π(m) is the length of the period of the Fibonacci sequence taken modulo m. Key properties:

1. π(m) ≤ 6m for all m
2. F(n) mod m = F(n mod π(m)) mod m
3. The period starts with F(0) mod m, F(1) mod m

Constraints

• 0 ≤ n ≤ 10^18
• 1 ≤ m ≤ 10^9
• For large n, use Pisano period optimization
• For small n, direct calculation is acceptable