finding nth term of fibonacci(1, 1, 2, 3, ...) in O(logn) time complexity

fibonacci_logn.cpp

#include<bits/stdc++.h>
#define MOD 1000000007
map<long long, long long> dp;
long long ans(long long n){
    if(n<=2) {
        dp[n]=1;
        return dp[n];
    }
    if(dp[n]) return dp[n];
    if(n%2==0){
        long long k = n/2;
        dp[n] = (((((long long)2*ans(k-1))%MOD + ((long long)ans(k))%MOD)%MOD)*ans(k))%MOD;
        // formula in even case of n
        // F_n = (2*F_n/2-1 + F_n/2)*F_n/2
    } else {
        long long k = (n+1)/2;
        dp[n] = (((long long)ans(k)*ans(k))%MOD + ((long long)ans(k-1)*ans(k-1))%MOD)%MOD;
        // formula in odd case of n
        // F_n = (F_(n+1)/2 ^2) + (F_(n+1)/2-1 ^2)
    }
    return dp[n]%MOD;
}