#include <cstdio>
#define prim 666013
using namespace std;
FILE *f=fopen("kfib.in","r");
FILE *g=fopen("kfib.out","w");
long long a[2][2],b[2][2],k;
long long x[2][2],y[2][2],z[2][2];

int masca=1<<30,nr=30,put[35];
bool ok=false;


void produs()
{
    int i,j,t;
    for (i=0;i<2;i++)
        for (j=0;j<2;j++)
            for (t=0;t<2;t++)
                z[i][j]+=1LL*x[i][t]*y[t][j];

    for (i=0;i<2;i++)
        for (j=0;j<2;j++) {
                x[i][j]=z[i][j]%prim;
                y[i][j]=0;z[i][j]=0;
    }
}


int main()
{
    int i,j,t,p;
    fscanf(f,"%d",&k);
    k--;

    while (k!=0){
        if ((masca&k)!=0){
            k-=masca;
            put[nr]=1;
        }
        masca=masca>>1;
        nr--;
    }

    a[0][1]=1;
    a[1][0]=1;
    a[1][1]=1;


    for (p=0;p<=31;p++){
        if (put[p]==1){
            if (ok==false) {
                for (i=0;i<2;i++) for (j=0;j<2;j++) x[i][j]=a[i][j];
                    ok=true;
            } else {
                for (i=0;i<2;i++)
                    for (j=0;j<2;j++) y[i][j]=a[i][j];
                        produs();
                }
            }
        for (i=0;i<2;i++) for (j=0;j<2;j++)
            for (t=0;t<2;t++)
                b[i][j]+=1LL*a[i][t]*a[t][j];
        for (i=0;i<2;i++)
            for (j=0;j<2;j++) {
                a[i][j]=b[i][j]%prim;
                b[i][j]=0;
            }
    }
    fprintf(g,"%d",x[1][1]);
    return 0;
}