#include <cstdio>
#define filein "kfib.in"
#define fileout "kfib.out"
#define X 666013
using namespace std;

long long m[2][2];
long long p[2][2];
int n;

void citire();
void generare();
void mm();
void pm();
void afisare();

int main()
{
    citire();
    generare();
    n-=2;
    while (n>0)
    {
        if (n%2==0)
        {
            mm();
            n=n/2;
        }
        else
        {
            n--;
            pm();
        }
    }
    afisare();
    return 0;
}

void citire()
{
    FILE *in;
    in=fopen(filein,"r");
    fscanf(in,"%d",&n);
    fclose(in);
}

void generare()
{
    m[0][0]=0;
    m[0][1]=1;
    m[1][0]=1;
    m[1][1]=1;
    p[0][0]=0;
    p[0][1]=1;
    p[1][0]=1;
    p[1][1]=1;
}

void mm()
{
    long long aux[2][2];
    aux[0][0]=(m[0][0]*m[0][0]+m[0][1]*m[1][0])%X;
    aux[0][1]=(m[0][0]*m[0][1]+m[0][1]*m[1][1])%X;
    aux[1][0]=(m[1][0]*m[0][0]+m[1][1]*m[1][0])%X;
    aux[1][1]=(m[1][0]*m[0][1]+m[1][1]*m[1][1])%X;
    m[0][0]=aux[0][0];
    m[0][1]=aux[0][1];
    m[1][0]=aux[1][0];
    m[1][1]=aux[1][1];
}

void pm()
{
    long long aux[2][2];
    aux[0][0]=(p[0][0]*m[0][0]+p[0][1]*m[1][0])%X;
    aux[0][1]=(p[0][0]*m[0][1]+p[0][1]*m[1][1])%X;
    aux[1][0]=(p[1][0]*m[0][0]+p[1][1]*m[1][0])%X;
    aux[1][1]=(p[1][0]*m[0][1]+p[1][1]*m[1][1])%X;
    p[0][0]=aux[0][0];
    p[0][1]=aux[0][1];
    p[1][0]=aux[1][0];
    p[1][1]=aux[1][1];
}

void afisare()
{
    FILE *out;
    out=fopen(fileout,"w");
    fprintf(out,"%lld",p[1][1]);
    fclose(out);
}