#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;
}