#include <stdio.h>

void matrixmultipl(long long a[2][2],long long b[2][2])
{
    long long result[2][2];
    result[0][0]=(a[0][0]*b[0][0]+a[0][1]*b[1][0])%666013;
    result[0][1]=(a[0][0]*b[0][1]+a[0][1]*b[1][1])%666013;
    result[1][0]=(a[1][0]*b[0][0]+a[1][1]*b[1][0])%666013;
    result[1][1]=(a[1][0]*b[0][1]+a[1][1]*b[1][1])%666013;
    a[0][0]=result[0][0];
    a[0][1]=result[0][1];
    a[1][0]=result[1][0];
    a[1][1]=result[1][1];
}

long long fibo(long long n)
{
    long long x[2][2],y[2][2];
    x[0][0]=0;
    x[0][1]=1;
    x[1][0]=1;
    x[1][1]=1;

    y[0][0]=1;
    y[0][1]=0;
    y[1][0]=0;
    y[1][1]=1;

    while(n)
    {
        if(n%2==1)
        {
            matrixmultipl(y,x);
        }
        matrixmultipl(x,x);
        n/=2;
    }
    return y[1][1];
}

int main()
{
    FILE *in =fopen("kfib.in","r");
    FILE *out = fopen("kfib.out","w");

    long long k;
    fscanf(in,"%lld",&k);
    k--;

    fprintf(out,"%lld",fibo(k));
}