#include <bits/stdc++.h>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
#define Mod 666013
int n,m;
struct s{
long long s[2][2];
} e;
s produs(s a, s b){
s z;
z.s[0][0]=((a.s[0][0]*b.s[0][0])%Mod+(a.s[0][1]*b.s[1][0])%Mod)%Mod;
z.s[0][1]=((a.s[0][0]*b.s[0][1])%Mod+(a.s[0][1]*b.s[1][1])%Mod)%Mod;
z.s[1][0]=((a.s[1][0]*b.s[0][0])%Mod+(a.s[1][1]*b.s[1][0])%Mod)%Mod;
z.s[1][1]=((a.s[1][0]*b.s[0][1])%Mod+(a.s[1][1]*b.s[1][1])%Mod)%Mod;
return z;
}
s Putere(s w,int n){
    if(n==1){
        return w;
    }
    if(n==0){
        return e;
    }
    if(n%2==0){
        s f=Putere(w,n/2);
        return produs(f,f);
    }
    else{
        return produs(Putere(w,n-1),w);
    }

}
int main(){
    int n;
    fin>>n;
    s q;
    q.s[0][0]=0;
    q.s[0][1]=1;
    q.s[1][0]=1;
    q.s[1][1]=1;
    e=q;
    q=Putere(q,n);
    fout<<q.s[0][1];
    return 0;
}