#include <bits/stdc++.h>

using namespace std;
ifstream fin ("kfib.in");
ofstream fout ("kfib.out");
const int MOD=666013;
long long k;
struct mat {
    long long M[2][2];
};
const mat matUnit={
    1,0,
    0,1
};
const mat matInit={
    1,1,
    1,0
};
mat produs (mat A,mat B)
{
    mat aux;
    aux.M[0][0]=(A.M[0][0]*B.M[0][0]+A.M[0][1]*B.M[1][0])%MOD;
    aux.M[0][1]=(A.M[0][0]*B.M[0][1]+A.M[0][1]*B.M[1][1])%MOD;
    aux.M[1][0]=(A.M[1][0]*B.M[0][0]+A.M[1][1]*B.M[1][0])%MOD;
    aux.M[1][1]=(A.M[1][0]*B.M[0][1]+A.M[1][1]*B.M[1][1])%MOD;
    return aux;
}
mat pow(mat M,long long k)
{
    if(k==0) return matUnit;
    if(k%2==0) return pow(produs(M,M),k/2);
    return produs(M,pow(produs(M,M),k/2));
}
int main()
{
    fin>>k;
    fout<<pow(matInit,k).M[1][0];
    return 0;
}