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

using namespace std;

const int MOD = 666013;
const char inf[] = "kfib.in";
const char outf[] = "kfib.out";

int n,z[3][3],fib[3][3];

FILE *in=fopen(inf,"r"),*out=fopen(outf,"w");

inline void mult(int a[][3],int b[][3],int c[][3])
{
    int i,j,k;
    for(i=0;i<2;i++)
        for(j=0;j<2;j++)
            for(k=0;k<2;k++)
                c[i][j]=(c[i][j]+1LL*a[i][k]*b[k][j])%MOD;
}

inline void pow(int p,int m[][3])
{
    int c[3][3],aux[3][3],i;
    memcpy(c,z,sizeof(z));
    m[0][0]=m[1][1]=1;
    for(i=0;(1<<i)<=p;i++)
        if(p && (1<<i))
        {
            memset(aux,0,sizeof(aux));
            mult(m,c,aux);
            memcpy(m,aux,sizeof(aux));
        }
    memset(aux,0,sizeof(aux));
    mult(c,c,aux);
    memcpy(c,aux,sizeof(c));
}

int main()
{
    fscanf(in,"%d",&n);
    z[0][0]=0;
    z[0][1]=z[1][0]=z[1][1]=1;
    pow(n-1,fib);
    fprintf(out,"%d",fib[1][1]);
    return 0;
}