Fibonacci - Formulae

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll MOD = 1000000007;
map<ll, ll> ma;

ll fib(ll n)
{
    if (n==0 or n==1) return 1;

    if (ma.find(n) != ma.end()) return ma[n];
    ma[n] = (fib((n+1)/2) * fib(n/2) + fib((n-1)/2) * fib((n-2)/2))%MOD;
    return ma[n];
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0);

    while (1)
    {
       ll n;
       cin >> n;
       if (n==0) cout << 0 << endl;
       else cout << fib(n-1) << endl;
    }
    return 0;
}