# include <fstream>
# define MOD 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
int d[3][3],I[3][3],n,i,j;
void inmulteste(int a[3][3],int b[3][3],int c[3][3]){
    int d[3][3];
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++){
            long long val=0;
            for(int k=1;k<=2;k++)
                val+=(1LL*a[i][k]*b[k][j]);
            d[i][j]=val%MOD;
        }
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            a[i][j]=d[i][j];
}
int main () {
    fin>>n;
    if(n==0){
        fout<<n<<"\n";
        return 0;
    }
    if(n<=2){
        fout<<"1\n";
        return 0;
    }
    n-=2;
    d[1][1]=d[1][2]=d[2][1]=I[1][1]=I[2][2]=1;
    for(i=0;i<30;i++){
        if((n&(1<<i)))
            inmulteste(I,d,I);
        inmulteste(d,d,d);
    }
    fout<<(I[1][1]+I[1][2])%MOD;
    return 0;
}