#include <fstream>
#define M 666013
using namespace std;
long long a,b;
struct matrice{ long long a11, a12, a21, a22;};
ifstream in("kfib.in"); ofstream out("kfib.out");
inline matrice inmult( matrice A, matrice B){
    matrice Z;
    Z.a11=(((A.a11%M) * (B.a11%M))%M + ((A.a12)%M * (B.a21)%M)%M)%M;
    Z.a12=(((A.a11%M) * (B.a12%M))%M + ((A.a12)%M * (B.a22)%M)%M)%M;
    Z.a21=(((A.a21%M) * (B.a11%M))%M + ((A.a22)%M * (B.a21)%M)%M)%M;
    Z.a22=(((A.a21%M) * (B.a12%M))%M + ((A.a22)%M * (B.a22)%M)%M)%M;
    return Z;
}
matrice put(matrice a, long long b){
    matrice p;
    p=(matrice){0,1,1,1};
    while(b){
        if(b&1) p=inmult(p,a);//p*=a;
        //a*=a;
        a=inmult(a,a);
        b/=2;
    }
    return p;
}
int main(){
    in>>b;
    matrice a;
    a=(matrice){0,1,1,1};
    b-=2;
    matrice R=put(a,b);
    out<<R.a22<<'\n';
    out.close();
    return 0;
}