#include <cstdio>

using namespace std;
long long p,k,i,cif[100],n,a[100],b[100],c[100],d[100],t;
int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%lld",&k);
    p=666013;
    k--;
    i=0;
    while(k!=0)
    {
      i++;
      cif[i]=k%2;
      k=k/2;
    }
    n=i;
    for(i=1;i<=n/2;i++){t=cif[i];cif[i]=cif[n-i+1];cif[n-i+1]=t;}
    a[0]=1;b[0]=0;c[0]=0;d[0]=1;
    for(i=1;i<=n;i++)
    if(cif[i]==0)
    {
        a[i]=(a[i-1]*a[i-1]+b[i-1]*c[i-1])%p;
        b[i]=(a[i-1]*b[i-1]+b[i-1]*d[i-1])%p;
        c[i]=(a[i-1]*c[i-1]+c[i-1]*d[i-1])%p;
        d[i]=(b[i-1]*c[i-1]+d[i-1]*d[i-1])%p;
    }
    else
    {
        a[i]=(a[i-1]*b[i-1]+b[i-1]*d[i-1])%p;
        b[i]=(a[i-1]*b[i-1]+b[i-1]*d[i-1]+a[i-1]*a[i-1]+b[i-1]*c[i-1])%p;
        c[i]=(b[i-1]*c[i-1]+d[i-1]*d[i-1])%p;
        d[i]=(b[i-1]*c[i-1]+d[i-1]*d[i-1]+a[i-1]*c[i-1]+c[i-1]*d[i-1])%p;
    }
    printf("%lld",d[n]);
    return 0;
}