#include <cstdio>

using namespace std;


void prodmatr(int a[2][2],int b[2][2])
{
    int c[2][2];
    c[0][0]=((long long)a[0][0]*b[0][0]+(long long)a[0][1]*b[1][0])%666013;
    c[0][1]=((long long)a[0][0]*b[0][1]+(long long)a[0][1]*b[1][1])%666013;
    c[1][0]=((long long)a[1][0]*b[0][0]+(long long)a[1][1]*b[1][0])%666013;
    c[1][1]=((long long)a[1][0]*b[0][1]+(long long)a[1][1]*b[1][1])%666013;
    b[0][0]=c[0][0];
    b[0][1]=c[0][1];
    b[1][0]=c[1][0];
    b[1][1]=c[1][1];
    return;
}


int main()
{
    FILE *f=fopen("kfib.in","r");
    int k;
    fscanf(f,"%d",&k);
    --k;
    fclose(f);
    f=fopen("kfib.out","w");
    int a[2][2]={{1,1},{1,0}},b[2][2]={{1,0},{0,1}};


    if(k==-1){fprintf(f,"0");return 0;}
    else if(k<2){fprintf(f,"1");return 0;}
    for(;k;k/=2){
            if(k%2)
            {
                prodmatr(a,b);
            }
    prodmatr(a,a);

    }
    fprintf(f,"%d",b[0][0]);
    return 0;
}