#include<bits/stdc++.h>
#define mod 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
int K;
void lgput(int putere){
    int z[3][3],aux[3][3],aux2[3][3],sol1[3][3],sol[3][3];
    memset(z,0,sizeof(z));
    memset(aux,0,sizeof(aux));
    memset(aux2,0,sizeof(aux2));
    memset(sol1,0,sizeof(sol1));
    memset(sol,0,sizeof(sol));
    z[0][0]=0;z[0][1]=1;
    z[1][0]=1;z[1][1]=1;
    aux[0][0]=0;aux[0][1]=1;
    aux[1][0]=1;aux[1][1]=1;
    sol[0][0]=sol[1][1]=1;
    while(putere)
        if(putere%2==1){
            aux2[0][0]=(sol[0][0]*aux[0][0]+sol[0][1]*aux[1][0])%mod;
            aux2[0][1]=(sol[0][0]*aux[0][1]+sol[0][1]*aux[1][1])%mod;
            aux2[1][0]=(sol[1][0]*aux[0][0]+sol[1][1]*aux[1][0])%mod;
            aux2[0][1]=(sol[1][0]*aux[0][1]+sol[1][1]*aux[1][1])%mod;
            sol[0][0]=aux2[0][0],sol[0][1]=aux2[0][1],sol[1][0]=aux2[1][0],sol[1][1]=aux2[1][1];
            --putere;
        }else{
            sol1[0][0]=(aux[0][0]*z[0][0]+aux[0][1]*z[1][0])%mod;
            sol1[0][1]=(aux[0][0]*z[0][1]+aux[0][1]*z[1][1])%mod;
            sol1[1][0]=(aux[1][0]*z[0][0]+aux[1][1]*z[1][0])%mod;
            sol1[0][1]=(aux[1][0]*z[0][1]+aux[1][1]*z[1][1])%mod;
            aux[0][0]=sol1[0][0],aux[0][1]=sol1[0][1],aux[1][0]=sol1[1][0],aux[1][1]=sol1[1][1];
            putere/=2;
        }
    g<<sol[1][1];
}
int main()
{
    f>>K;
    lgput(K-1);
    return 0;
}