Fibonacci2

#include <iostream>
#define M 666013;
using namespace std;
struct Mat /// Struct ce retine o matrice 2x2
{
    int mat[2][2];
};
const Mat nullMat= /// Elementul neutru la inmultirea matricelor 2x2
{
    {{1, 0},
     {0, 1}}
};
const Mat initMat= /// Matricea pe care o ridicam la puterea k
{
    {{1, 1},
     {1, 0}}
};

Mat prod(Mat a,Mat b) /// Functie ce calculeaza a*b
{
    Mat ret;
    ret.mat[0][0]=(1LL*a.mat[0][0]*b.mat[0][0]+1LL*a.mat[0][1]*b.mat[1][0])%M;
    ret.mat[0][1]=(1LL*a.mat[0][0]*b.mat[0][1]+1LL*a.mat[0][1]*b.mat[1][1])%M;
    ret.mat[1][0]=(1LL*a.mat[1][0]*b.mat[0][0]+1LL*a.mat[1][1]*b.mat[1][0])%M;
    ret.mat[1][1]=(1LL*a.mat[1][0]*b.mat[0][1]+1LL*a.mat[1][1]*b.mat[1][1])%M;
    return ret;
}

Mat pwr(Mat mat,int n) /// Functie recursiva pentru calcularea mat^n
{
    if(!n)
        return nullMat;
    if(n&1)
        return prod(mat,pwr(prod(mat,mat),n>>1));
    return pwr(prod(mat,mat),n>>1);
}

int main()
{
    int n;
    cin>>n;
    cout<<pwr(initMat,n).mat[0][1]<<'\n';
    return 0;
}