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