#include <fstream>

using namespace std;

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

struct mat{
    long long a[2][2];
};

mat operator*(const mat& m1,const mat& m2){
    mat s;
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++){
            s.a[i][j]=0;
            for(int t=0;t<2;t++)
                s.a[i][j]=(s.a[i][j]+m1.a[i][t]*m2.a[t][j])%666013;
        }

    return s;
}

mat exp(mat a,int k){
    if(k==1) return a;

    mat ax=exp(a,k/2);
    ax=ax*ax;
    if(k%2) ax=ax*a;
    return ax;
}

int main()
{
    mat un;
    un.a[0][0]=0;
    un.a[0][1]=1;
    un.a[1][0]=1;
    un.a[1][1]=1;

    int k;
    f>>k;

    if(k<=3){
        switch(k){
            case 0:g<<0; break;
            case 1:g<<1; break;
            case 2:g<<1; break;
            case 3:g<<2; break;
        }
        return 0;
    }

    un=exp(un,k-3);

    long long s;
    s=(un.a[0][1]+(2*un.a[1][1])%666013)%666013;

    g<<s;

    return 0;
}