Kth Fibonacci

//https://www.pbinfo.ro/articole/19411/Matrice%20Fibonacci
#include <bits/stdc++.h>
#define MOD 666013

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

long long a[5][5], b[5][5], c[5][5], sol[5][5];

void inmultire_matrice(long long a[5][5],long long b[5][5]) {
    for(int i = 1; i <=2; ++i)
        for(int j = 1; j <= 2; ++j) {
            long long s = 0;
            for(int k = 1; k <= 2; ++k)
                s = (s + a[i][k] * b[k][j]) % MOD;
            c[i][j] = s % MOD;
        }
    for(int i = 1; i <= 2; ++i)
        for(int j = 1; j <= 2; ++j)
            a[i][j] = c[i][j];
}

void pow_log(long long k) {
    while(k > 0) {
        if(k & 1)
            inmultire_matrice(sol, b);
        inmultire_matrice(b, b);
        k >>= 1;
    }
}

int main() {
    long long n;
    f >> n;
    if(n == 0)
        g << 0;
    else {
        a[1][2] = b[1][2] = b[2][1] = b[2][2] = sol[1][1] = sol[2][2] = 1;
        pow_log(n - 1);
        inmultire_matrice(a, sol);
        g << a[1][2];
    }
}