#include<fstream>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
long long mi[3][3]={
    {0,0,0},
    {0,0,1},
    {0,1,1}};
long long MOD=666013;
long long fbn(int p){
    long long cmi[3][3],i,j;
    long long a11,a12,a21,a22;
    cmi[1][1]=1;cmi[1][2]=0;cmi[2][1]=0;cmi[2][2]=1;
    while(p){
        if(p&1){
            a11=(cmi[1][1]*mi[1][1]+cmi[1][2]*mi[2][1])%MOD;
            a12=(cmi[1][1]*mi[1][2]+cmi[1][2]*mi[2][2])%MOD;
            a21=(cmi[2][1]*mi[1][1]+cmi[2][2]*mi[2][1])%MOD;
            a22=(cmi[2][1]*mi[1][2]+cmi[2][2]*mi[2][2])%MOD;
            cmi[1][1]=a11;cmi[1][2]=a12;cmi[2][1]=a21;cmi[2][2]=a22;
        }
        a11=(mi[1][1]*mi[1][1]+mi[1][2]*mi[2][1])%MOD;
        a12=(mi[1][1]*mi[1][2]+mi[1][2]*mi[2][2])%MOD;
        a21=(mi[2][1]*mi[1][1]+mi[2][2]*mi[2][1])%MOD;
        a22=(mi[2][1]*mi[1][2]+mi[2][2]*mi[2][2])%MOD;
        mi[1][1]=a11;mi[1][2]=a12;mi[2][1]=a21;mi[2][2]=a22;
        p>>=1;
    }
    return cmi[2][2];

}
int main(){
    int k;
    fin>>k;
    fout<<fbn(k-1)<<'\n';
    fin.close();
    fout.close();
}