#include <fstream>
#include <iostream>
#define MOD 666013
using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

long long k;

struct mat
{
    long long val[4][4];
} a;

mat inmultire(mat a,mat b)
{mat c;
c.val[1][1]=(a.val[1][1]*b.val[1][1]+a.val[1][2]*b.val[2][1])%MOD;
c.val[1][2]=(a.val[1][1]*b.val[1][2]+a.val[1][2]*b.val[2][2])%MOD;
c.val[2][1]=(a.val[2][1]*b.val[1][1]+a.val[2][2]*b.val[2][1])%MOD;
c.val[2][2]=(a.val[2][1]*b.val[1][2]+a.val[2][2]*b.val[2][2])%MOD;
return c;
}

mat explog(mat x,long long p)
{
    if(p==1) return x;
    mat X=explog(x,p/2);
    if (p%2)
return inmultire(inmultire(X,X),x);
    return inmultire(X,X);
}

int main()
{
    cin>>k;
    a.val[1][1]=0;
    a.val[1][2]=a.val[2][1]=a.val[2][2]=1;
    mat c=explog(a,k);

    long long rez=(0*c.val[1][1]+1*c.val[2][1])%MOD;

    cout<<rez;
}