#include <cstdio>

using namespace std;

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

int k,d[3][3];

int main()
{
    FILE *f=fopen("kfib.in","r");
    fscanf(f,"%d",&k);
    fclose(f);
    int i[3][3],m[3][3],r,c[3][3];
    i[1][1]=1;i[1][2]=0;i[2][1]=0;i[2][2]=1;
    m[1][1]=0;m[1][2]=1;m[2][1]=1;m[2][2]=1;
    do
    {
        r=k%2;
        k/=2;
        if(r)
            inmultire(i,m,c);
        inmultire(m,m,d);
        m[1][1]=d[1][1];
        m[1][2]=d[1][2];
        m[2][1]=d[2][1];
        m[2][2]=d[2][2];
    }while(k);
    int t,j;
    f=fopen("kfib.out","w");
    fprintf(f,"%d",m[1][1]);
    return 0;
}