#include <stdio.h>
#include <stdlib.h>
#define mod 666013
#define ll long long

using namespace std;

ll m[2][2];
ll f[2];

void putere(){
    ll aux[2][2];
    aux[0][0]=(m[0][0]*m[0][0]+m[0][1]*m[1][0])%mod;
    aux[0][1]=(m[0][0]*m[0][1]+m[0][1]*m[1][1])%mod;
    aux[1][0]=(m[1][0]*m[0][0]+m[1][1]*m[1][0])%mod;
    aux[1][1]=(m[1][0]*m[0][1]+m[1][1]*m[1][1])%mod;
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            m[i][j]=aux[i][j];
}

void pow(ll k){
    while(k>0){
        if(k%2==1){
            ll aux[2];
            aux[0]=(f[0]*m[0][0]+f[1]*m[0][1])%mod;
            aux[1]=(f[0]*m[1][0]+f[1]*m[1][1])%mod;
            f[0]=aux[0];
            f[1]=aux[1];
        }
        k/=2;
        putere();
    }
}

int main()
{
    FILE *fin, *fout;
    ll n;
    fin=fopen("kfib.in","r");
    fout=fopen("kfib.out","w");
    fscanf(fin,"%lld",&n);
    if(n==0)
        fprintf(fout,"0");
    else if(n==1 || n==2)
        fprintf(fout,"1");
    else{
        m[0][1]=m[1][0]=m[1][1]=1;
        f[0]=1;
        f[1]=1;
        n-=2;
        pow(n);
        fprintf(fout,"%lld",f[1]);
    }
    return 0;
}