Fibonacci - Matrix

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

typedef unsigned long long ull;

void power(ull F[2][2], ull n);
void multiply(ull F[2][2], ull M[2][2]);
const ull MOD = 1000000007;

ull solve(ull n)
{
    if (n==0) return 0;

    ull F[2][2] {{1, 1}, {1, 0}};
    power(F, n-1);
    return F[0][0];
}

void power(ull F[2][2], ull n)
{
    if (n==0 or n==1) return;

    ull M[2][2] {{1, 1}, {1, 0}};
    power(F, n/2);
    multiply(F, F);

    if (n%2!=0)
        multiply(F, M);
}

void multiply(ull F[2][2], ull M[2][2])
{
   ull x  = F[0][0]*M[0][0] + F[0][1]*M[1][0];
   ull y  = F[0][0]*M[0][1] + F[0][1]*M[1][1];
   ull z  = F[1][0]*M[0][0] + F[1][1]*M[1][0];
   ull w  = F[1][0]*M[0][1] + F[1][1]*M[1][1];

    F[0][0] = x%MOD;
    F[0][1] = y%MOD;
    F[1][0] = z%MOD;
    F[1][1] = w%MOD;
}


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

    ull n; cin >> n;
    cout << solve(n);
    return 0;
}