#include <cstdio>
#define MOD 666013
using namespace std;
int m[2][2]={
    {1,1},
    {1,0}
};
int en[2][2]={
    {1,0},
    {0,1}
};
int m2[2][1]={
    {1},
    {0}
};
int a[2][2],b[2][2],c[2][2],p[2][2];
void cop (int a[2][2],int b[2][2]){
    for (int i=0;i<2;i++)
        for (int j=0;j<2;j++)
            a[i][j]=b[i][j];
}
void inmult (int a[2][2],int b[2][2]){
    for (int i=0;i<2;i++){
        for (int j=0;j<2;j++){
            c[i][j]=0;
            for (int ii=0;ii<2;ii++)
                c[i][j]=(c[i][j] + ((long long)a[i][ii]*b[ii][j])%MOD)%MOD;
        }
    }
}
void inmult2 (int a[2][2],int b[2][1]){
    for (int i=0;i<2;i++){
        for (int j=0;j<1;j++){
            c[i][j]=0;
            for (int ii=0;ii<2;ii++)
                c[i][j]=(c[i][j] + ((long long)a[i][ii]*b[ii][j])%MOD)%MOD;
        }
    }
}
int main()
{
    FILE *fin=fopen ("kfib.in","r");
    FILE *fout=fopen ("kfib.out","w");
    int k;
    fscanf (fin,"%d",&k);
    if (k<2){
        fprintf (fout,"%d",k);
        return 0;
    }
    k--;
    cop (p,en);
    cop (a,m);
    while (k){
        if (k%2){
            inmult (p,a);
            cop (p,c);
        }
        inmult (a,a);
        cop (a,c);
        k/=2;
    }
    inmult2 (p,m2);
    cop (a,c);
    //sol=0;
    //for (j=0;j<2;j++)
      //  sol=(sol+a[0][j])%MOD;
    fprintf (fout,"%d",a[0][0]);
    return 0;
}