#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]+(long long)a[1][2]*b[2][1])%666013;
    c[1][2]=((long long)a[1][1]*b[1][2]+(long long)a[1][2]*b[2][2])%666013;
    c[2][1]=((long long)a[2][1]*b[1][1]+(long long)a[2][2]*b[2][1])%666013;
    c[2][2]=((long long)a[2][1]*b[1][2]+(long long)a[2][2]*b[2][2])%666013;
}

void copymat(int m[][3],int d[][3])
{
    m[1][1]=d[1][1];
    m[1][2]=d[1][2];
    m[2][1]=d[2][1];
    m[2][2]=d[2][2];
}

int k,d[3][3];

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