#include <iostream>
#include <stdio.h>


using namespace std;

FILE *f=fopen("kfib.in","r");
FILE *g=fopen("kfib.out","w");

unsigned long long k;
int nr;



void prod(int a[3][3],int b[3][3])
{
    int i,j,aux[3][3];
    long long cn;
    for(i=0;i<=2;i++)
    for(j=0;j<=2;j++)
    aux[i][j]=0;
    for(i=1;i<=2;i++)
       for(j=1;j<=2;j++)
          for(k=1;k<=2;k++)
          {
            cn=((long long)aux[i][j]+((long long)a[i][k]*b[k][j]))%nr;
            aux[i][j]=cn;
          }
    for(i=1;i<=2;i++)
    for(j=1;j<=2;j++)
    a[i][j]=aux[i][j];
    return;
}


void ridic(int k)
{
    int j,i,p[3][3],val[3][3];
    for(i=0;i<=2;i++)
    for(j=0;j<=2;j++)
    {
        p[i][j]=0;
        val[i][j]=0;
    }
    p[1][1]=p[1][2]=p[2][1]=1;
    p[2][2]=0;
    val[1][1]=val[2][2]=1;
    for(i=0;i<=31;i++,prod(p,p))
       if(k&(1<<i)) prod(val,p);

    fprintf(g,"%d",val[1][1]+val[1][2]);


    return;
}


int main()
{
    fscanf(f,"%d",&k);
    nr=666013;
    if(k>2) ridic(k-2); else fprintf(g,"%d",1);


    fclose(g);
    return 0;
}