#include <fstream>

using namespace std;
int a[4][4],mat[10][10],rez[10][10],aux[10][10];
int mod=666013,cnt=0;
void lgput(long long put){
    for(long long i=put;i>=1;i>>=1){
        if(i&1){
            cnt++;
            if(cnt==1){
                rez[1][1]=mat[1][1];rez[1][2]=mat[1][2];rez[2][1]=mat[2][1];rez[2][2]=mat[2][2];
            }
            else{
                aux[1][1]=(1LL*rez[1][1]*mat[1][1]+1LL*rez[1][2]*mat[2][1])%mod;
                aux[1][2]=(1LL*rez[1][1]*mat[1][2]+1LL*rez[1][2]*mat[2][2])%mod;
                aux[2][1]=(1LL*rez[2][1]*mat[1][1]+1LL*rez[2][2]*mat[2][1])%mod;
                aux[2][2]=(1LL*rez[2][1]*mat[1][2]+1LL*rez[2][2]*mat[2][2])%mod;
                rez[1][1]=aux[1][1];rez[1][2]=aux[1][2];rez[2][1]=aux[2][1];rez[2][2]=aux[2][2];
            }
        }
        aux[1][1]=(1LL*mat[1][1]*mat[1][1]+1LL*mat[1][2]*mat[2][1])%mod;
        aux[1][2]=(1LL*mat[1][1]*mat[1][2]+1LL*mat[1][2]*mat[2][2])%mod;
        aux[2][1]=(1LL*mat[2][1]*mat[1][1]+1LL*mat[2][2]*mat[2][1])%mod;
        aux[2][2]=(1LL*mat[2][1]*mat[1][2]+1LL*mat[2][2]*mat[2][2])%mod;
        mat[1][1]=aux[1][1];mat[1][2]=aux[1][2];mat[2][1]=aux[2][1];mat[2][2]=aux[2][2];
    }
}
int main()
{
    ifstream fin("kfib.in");
    ofstream fout("kfib.out");
    int k;fin>>k;
    if(k==0){fout<<"0"<<'\n';}
    else if(k==1){fout<<"1"<<'\n';}
    else{
        a[1][1]=0;a[1][2]=1;mat[1][1]=0;mat[1][2]=1;mat[2][1]=1;mat[2][2]=1;
        lgput(k-1);
        aux[1][1]=(1LL*a[1][1]*rez[1][1]+1LL*a[1][2]*rez[2][1])%mod;
        aux[1][2]=(1LL*a[1][1]*rez[1][2]+1LL*a[1][2]*rez[2][2])%mod;
        fout<<aux[1][2]<<'\n';
    }
    return 0;
}