Fibonacci

ll Fib (ll n) {
   if (n == 0) return 0;
   if (n == 1 || n == 2)
        return F[n] = 1;
    if (F.count(n)) return F[n];
    ll k = (n % 2) ? ((n + 1) / 2) : (n / 2);
    if (n % 2) return F[n] = (bp (Fib(k), 2) + bp (Fib(k - 1), 2)) % MOD;
    return F[n] = (((2 * Fib (k - 1) + Fib (k)) % MOD) * Fib (k)) % MOD;
}