#include <stdio.h>
#include <stdlib.h>
#define mod %666013

int k;
long long mat[2][2]={{1L,1L},{1L,0L}};

void inmultire(long long a[2][2],long long b[2][2])
{
    long long m[2][2];
    m[0][0]=a[0][0];
    m[0][1]=a[0][1];
    m[1][0]=a[1][0];
    m[1][1]=a[1][1];

    m[0][0]=((a[0][0]*b[0][0])mod+(a[0][1]*b[1][0])mod)mod;
    m[0][1]=((a[0][0]*b[0][1])mod+(a[0][1]*b[1][1])mod)mod;
    m[1][0]=((a[1][0]*b[0][0])mod+(a[1][1]*b[1][0])mod)mod;
    m[1][1]=((a[1][0]*b[0][1])mod+(a[1][1]*b[1][1])mod)mod;

    a[0][0]=m[0][0];
    a[0][1]=m[0][1];
    a[1][0]=m[1][0];
    a[1][1]=m[1][1];
}

int main()
{
    FILE *f=fopen("kfib.in","r");
    FILE *g=fopen("kfib.out","w");
    int i,p;
    long long rez[2][2]={{1L,0L},{0L,1L}};

    fscanf(f,"%d",&k);
    p=k-2;

    for (i=0;(1<<i)<=p;i++)
    {
        if (((1<<i)&p)!=0)
            inmultire(rez,mat);
        inmultire(mat,mat);
    }

    fprintf(g,"%d\n",(int)((rez[0][0]+rez[0][1])mod));
    fclose(f);
    fclose(g);
    return 0;
}