#include <bits/stdc++.h>
#define int long long
using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

const int mod=666013;

int M[2][2]={{1,1},{1,0}};
int F[2][2]={{1,1},{1,0}};

void multiply(int F[2][2],int M[2][2]){
    int x=F[0][0]*M[0][0]+F[0][1]*M[1][0];
    int y=F[0][0]*M[0][1]+F[0][1]*M[1][1];
    int z=F[1][0]*M[0][0]+F[1][1]*M[1][0];
    int w=F[1][0]*M[0][1]+F[1][1]*M[1][1];
    F[0][0]=x%mod;
    F[0][1]=y%mod;
    F[1][0]=z%mod;
    F[1][1]=w%mod;
}

void power(int n){
    if(n<=1){
        return;
    }
    power(n/2);
    multiply(F,F);
    if(n%2==1){
        multiply(F,M);
    }
}

signed main(){
    int k;
    fin>>k;
    power(k-1);
    fout<<F[0][0];
}