#include<cstdio>
#include<cstdlib>
#define mod 666013
#define ll long long int
void initMatr(ll a[2][2],ll b[2][2])
{
     a[0][0]=b[0][0]=0;
     a[0][1]=b[0][1]=1;
     a[1][0]=b[1][0]=1;
     a[1][1]=b[1][1]=1;
}
void inmMatr(ll a[2][2],ll b[2][2])
{
     ll x,y,z,t;
     x=(a[0][0]*b[0][0]+a[0][1]*b[1][0])%mod;
     y=(a[0][0]*b[0][1]+a[0][1]*b[1][1])%mod;
     z=(a[1][0]*b[0][0]+a[1][1]*b[1][0])%mod;
     t=(a[1][0]*b[0][1]+a[1][1]*b[1][1])%mod;
     a[0][0]=x;
     a[0][1]=y;
     a[1][0]=z;
     a[1][1]=t;
}
int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    ll k,i,j,a[2][2],b[2][2];
    scanf("%lld",&k);
    initMatr(a,b);
    if(k==1||k==2) b[1][1]=1;
    if(k==3) b[1][1]=2;
    if(k>3){
            k=k-2;
            for(i=0;(1<<i)<=k;i++)
            {
                                  if((1<<i)&k)
                                  inmMatr(b,a);
                                  inmMatr(a,a);
            }
            }
    printf("%lld",b[1][1]);
    return 0;
}