#include <fstream>
#include <iostream>
using namespace std;
const int mod=666013;

class matrice{
    public:
    int a,b,c,d;
    matrice mul(matrice x){
        matrice temp;
        temp.a=(a*x.a+b*x.c)%mod;
        temp.c=(c*x.a+d*x.c)%mod;
        temp.b=(a*x.b+b*x.d)%mod;
        temp.d=(c*x.b+d*x.d)%mod;
        return temp;
    }
    void scrie(){
        cout<<"\n"<<a<<"  "<<b<<"\n"<<c<<"  "<<d<<"\n";
    }
}base,unit;




matrice rec(int n){
    if(n){
        matrice temp=rec(n/2);
        temp=temp.mul(temp);

        if(n%2){
            temp=temp.mul(base);
        }
        return temp;
    }else{
        return unit;
    }
}

int main(){
    ifstream in("kfib.in");
    ofstream out("kfib.out");
    base.a=0;base.b=1;base.c=1;base.d=1;
    unit.a=1;unit.b=0;unit.c=0;unit.d=1;
    int n;in>>n;

    out<<rec(n).b;

}