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

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

const long long MOD=666013;

int k;
vector <vector <long long>> m(2, vector <long long>(2));

/*void afis(vector <vector <long long>> a){
cout<<endl;
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            cout<<a[i][j]<<' ';
        }
        cout<<endl;
    }
}*/

vector <vector <long long>> Inmultire(vector <vector <long long>> a, vector <vector <long long>> b){
    vector <vector <long long>> c(2, vector<long long>(2, 0));
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            for(int k=0;k<2;k++){
                c[i][j]=(c[i][j]+((a[i][k]%MOD)*(b[k][j]%MOD)%MOD))%MOD;
            }
        }
    }
    /*cout<<"\nINMULTIRE\n";
    afis(a);
    afis(b);
    afis(c);*/
    return c;
}

vector <vector <long long>> Ridicare(vector <vector <long long>> baza, int e){
    vector <vector <long long>> r(2, vector <long long>(2));
    r[0][0]=r[1][1]=1;
    r[0][1]=r[1][0]=0;

    while(e){
        //cout<<endl<<e<<endl;
        if(e%2==1){
            //cout<<"r"<<endl;
            e--;
            r=Inmultire(r, baza);
        }

        else{
            //cout<<"m"<<endl;
            baza = Inmultire(baza,baza);
            e/=2;
        }
    }
    //cout<<"rez"<<endl;
    //r=Inmultire(baza, r);
    return r;
}


int main(){
    fin>>k;

    m[0][0]=m[0][1]=m[1][0]=1;

    m=Ridicare(m, k-2);

    vector <vector <long long>> r(2, vector<long long>(2));
    r[0][0]=r[0][1]=1;
    r[1][0]=r[1][1]=0;


    //cout<<"f"<<endl;
    r=Inmultire(r, m);


    fout<<r[0][0];

    return 0;
}