#include <iostream>
#include <fstream>
#include <array>

using namespace std;

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

const int mod=666013;
int n;

struct MAT22{
    unsigned long long M[2][2]={{1,0},{0,1}};
    MAT22 operator*(MAT22 X) const{
        MAT22 T;
        T.M[0][0]=X.M[0][0]*M[0][0]%mod+X.M[0][1]*M[1][0]%mod;
        T.M[0][1]=X.M[0][0]*M[0][1]%mod+X.M[0][1]*M[1][1]%mod;
        T.M[1][0]=X.M[1][0]*M[0][0]%mod+X.M[1][1]*M[1][0]%mod;
        T.M[1][1]=X.M[1][0]*M[0][1]%mod+X.M[1][1]*M[1][1]%mod;
        return T;
    }
}I2;
MAT22 powm(MAT22 X, int pow){
    if(pow==0)
        return I2;
    if(pow==1)
        return X;
    if(pow%2==0)
        return powm(X*X,pow/2);
    return X*powm(X*X,(pow-1)/2);
}
void read(){
    in>>n;
}
void solve(){
    MAT22 FIB;
    FIB.M[0][0]=0;
    FIB.M[0][1]=1;
    FIB.M[1][0]=1;
    FIB.M[1][1]=1;
    FIB=powm(FIB,n);
    out<<FIB.M[0][1];
}
int main(){
    read();
    solve();
    return 0;
}