The Pisano period approach is not so hard, but lengthy - you need basically everything from basic number theory.
We can compute Fibonacci numbers by matrix exponentiation. What’s the result of multiplying (vertical lines denote matrices, not determinants)
|1 1| |x|
|1 0| |y| ?
There is no formula for the Pisano period, but then again, if there was, this wouldn’t really be a programming question :D. There are several theorems that can help us: Chinese remainder theorem states that if you decompose M into a product of prime powers, then the period is just LCM of periods modulo those prime powers; for a prime power p^a (a > 1), the period pi(p^a) will be p^(a-1) * pi§ (this doesn’t hold generally, but so far no number for which it doesn’t hold has been found, and we can hope that the contest organizers didn’t make a massive discovery in mathematics :D), and for a prime p, the period pi§ will divide either p-1 or 2 * (p+1) for every p except 2 and 5 (for which finding the period is trivial). You can just bruteforce all divisors of p-1 and 2*(p+2), then, and choose the smallest period.
All that’s left now is to compute nCr modulo pi(M). nCr=n!/r!(n-r)!; for every prime factor of pi(M), find which power of it divides nCr, compute “reduced” n!, r! and (n-r)! %pi(M) after dividing them by maximum powers of those prime factors, compute the modular inverse of reduced r!(n-r)!, compute the reduced nCr and multiply it back by the correct powers of prime factors of pi(M). All of it mod pi(M). Then just find its corresponding Fibonacci number.