#include <stdio.h>
#define mod 666013
 
long long I[3][3], CI[3][3], rez[3][3], f[2][3];
void ridiclaput(int exp)
{
    int i,j;
    rez[1][1]=1;
    rez[2][2]=1;
    while(exp){
        if(exp%2==0){
            CI[1][1]=(I[1][1]*I[1][1]+I[1][2]*I[2][1])%mod;
            CI[1][2]=(I[1][1]*I[1][2]+I[1][2]*I[2][2])%mod;
            CI[2][1]=(I[2][1]*I[1][1]+I[2][2]*I[2][1])%mod;
            CI[2][2]=(I[2][1]*I[1][2]+I[2][2]*I[2][2])%mod;
            for(i=1;i<=2;i++)
                for(j=1;j<=2;j++)
                I[i][j]=CI[i][j];
            exp/=2;
        }
        else{
            CI[1][1]=(rez[1][1]*I[1][1]+rez[1][2]*I[2][1])%mod;
            CI[1][2]=(rez[1][1]*I[1][2]+rez[1][2]*I[2][2])%mod;
            CI[2][1]=(rez[2][1]*I[1][1]+rez[2][2]*I[2][1])%mod;
            CI[2][2]=(rez[2][1]*I[1][2]+rez[2][2]*I[2][2])%mod;
            for(i=1;i<=2;i++)
                for(j=1;j<=2;j++)
                rez[i][j]=CI[i][j];
            exp--;
            }
        }
}
int main()
{
    int n;
    FILE *fin,*fout;
    fin=fopen("kfib.in", "r");
    fscanf(fin,"%d", &n);
    fclose(fin);
    f[1][1]=0;
    f[1][2]=1;
    I[2][1]=1;
    I[1][2]=1;
    I[2][2]=1;
    ridiclaput(n-1);
    CI[1][1]=(f[1][1]*rez[1][1]+f[1][2]*rez[2][1])%mod;
    CI[1][2]=(f[1][1]*rez[1][2]+f[1][2]*rez[2][2])%mod;
    fout=fopen("kfib.out","w");
    fprintf(fout,"%lld", CI[1][2]);
    fclose(fout);
    return 0;
}