#include<fstream>
using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
const int MOD = 666013;
struct mat{
    int a[3][3];
    mat(){}
    mat(int aa,int ab,int ba,int bb){
        a[1][1]=aa;
        a[1][2]=ab;
        a[2][1]=ba;
        a[2][2]=bb;
    }
    mat operator * (mat X){
        mat S;
        S.a[1][1]= ( 1LL*a[1][1]*X.a[1][1] + 1LL*a[1][2]*X.a[2][1] )%MOD;
        S.a[1][2]= ( 1LL*a[1][1]*X.a[1][2] + 1LL*a[1][2]*X.a[2][2] )%MOD;
        S.a[2][1]= ( 1LL*a[2][1]*X.a[1][1] + 1LL*a[2][2]*X.a[2][1] )%MOD;
        S.a[2][2]= ( 1LL*a[2][1]*X.a[1][2] + 1LL*a[2][2]*X.a[2][2] )%MOD;
        return S;
    }
};
mat logpow(mat B,int k){
    mat A=mat(1,0,0,1);
    for(int e=0;(1<<e)<=k;e++){
        if(k&(1<<e)) A=A*B;
        B=B*B;
    }
    return A;
}
int K;
int main(){
    mat Z=mat(1,1,1,0);
    in>>K;
    Z=logpow(Z,K-2);
    out<<(Z.a[1][1]+Z.a[2][1])%MOD;
    return 0;
}