nTh Fibonacci number

const int mod = 1e9 + 7;
#define int long long
map<int, int> F;
// F[0] = 1, F[1] = 1;
int fib(int n) {
    if (F.count(n)) return F[n];
    int k=n/2;
    if (n%2==0) {
        return F[n] = (fib(k)*fib(k) + fib(k-1)*fib(k-1)) % mod;
    } else {
        return F[n] = (fib(k)*fib(k+1) + fib(k-1)*fib(k)) % mod;
    }
}