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