#include <iostream>
#include <cstdio>
using namespace std;
long long P=666013,pp=333007;
struct intregi
{
    long long a;
    long long b;
};

long long puteremod(int n)
{
    if(n==1)return pp;
    if(n%2){ return (pp*puteremod(n-1))%P;   }
    else return (puteremod(n>>1)*puteremod(n>>1))%P;

}


intregi produs(intregi x,intregi y)
{

    intregi aux;
    aux.a= x.a*y.a + 5*x.b*y.b;
    aux.a=(aux.a)%P;
    aux.b=x.a*y.b+x.b*y.a;
    aux.b=(aux.b)%P;
    return aux;
}


intregi putere(intregi z,int n)
{

    if(n==1)return z;
    else {

        if( n%2 ) return produs(z,putere(z,n-1));
        else
        return produs(putere(z,n>>1),putere(z,n>>1));



        }
}

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


intregi z;


z.a=1; z.b=1;
long long n;
scanf("%lld",&n);
if(n==1)printf("1");
else{

z=putere(z,n);
long long fibo=z.b;
//fibo=fibo>>(n-1);
fibo=fibo*puteremod(n-1);
fibo=fibo%P;
printf("%lld",fibo);
}

    return 0;
}