#include <bits/stdc++.h>

using namespace std;

#define TITLE "kfib"

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

#define ll long long
#define MOD 666013

struct Mat
{
    ll mat[2][2];
};

Mat initialmatrix =
{
    {   {0,1},
        {1,1}
    }
};

Mat zeromatrix =
{
    {   {0,1},
        {1,0}
    }
};

Mat matrixproduce (Mat a, Mat b)
{
    Mat ans;
    ans.mat[0][0]=(a.mat[0][0]*b.mat[0][0]+a.mat[0][1]*b.mat[1][0])%MOD;
    ans.mat[0][1]=(a.mat[0][0]*b.mat[0][1]+a.mat[0][1]*b.mat[1][1])%MOD;
    ans.mat[1][0]=(a.mat[1][0]*b.mat[0][0]+a.mat[1][1]*b.mat[1][0])%MOD;
    ans.mat[1][1]=(a.mat[1][0]*b.mat[0][1]+a.mat[1][1]*b.mat[1][1])%MOD;
    return ans;
}

Mat matrixbinpow (Mat a, ll p)
{
    Mat ans=zeromatrix;
    while(p)
    {
        if(p%2==1)
            ans=matrixproduce(ans,a);
        a=matrixproduce(a,a);
        p/=2;
    }
    return ans;
}

int main()
{
    ll n;
    f>>n;
    Mat answer=matrixbinpow(initialmatrix,n);
    g<<answer.mat[1][1];
    return 0;
}