#include<cstdio>
#define M 666013
using namespace std;

class mazi{
public:
    long long a,b;
    int rad;

    mazi operator *(mazi x){
        mazi r;

        r.rad=rad;
        r.a=(a*x.a+b*x.b*rad)%M;
        r.b=(a*x.b+b*x.a)%M;

        return r;
    }

    mazi operator ^(int n){
        mazi r;

        if (n==0){
            r.a=1;
            r.b=0;
            r.rad=rad;
        }
        else
        if (n&1) r=(*this)*((*this)^(n-1));
        else {
            r=(*this)^(n/2);
            r=r*r;
        }

        return r;
    }
};


int ridPut(long long a,long long n){
    if (n==0) return 1;
    else
    if (n&1) return (a*ridPut(a,n-1))%M;
    else return ridPut((a*a)%M,n/2);
}

int prec[]={0,1,1,2,3,5,8,13,21,34,55};

int main(){
    freopen ("kfib.in","r",stdin);
    freopen ("kfib.out","w",stdout);
    long long k;
    long long r;

    scanf ("%lld",&k);

    if (k<10)
        printf ("%d\n",prec[k]);
    else {
        mazi aux;
        aux.a=1;
        aux.b=1;
        aux.rad=5;

        aux=aux^k;
        r=(2*aux.b)%M;
        r=(r*ridPut(2,k*(M-2)))%M;

        printf ("%lld\n",r);
    }

    return 0;
}