#include<cstdio>
#define M 666013
long long k,a1,a2,a3,a4=2,b1,b2,b3,b4,d1,d2,d3,d4,c1,c2,c3,c4;
int v[1000001],i,j;
int main()
{freopen("kfib.in","r",stdin);
freopen("kfib.out","w",stdout);
scanf("%lld",&k),k--;
while(k)
      v[i++]=k%2,k/=2;
d2=d3=d4=a1=a2=a3=1;
for(j=i-2;j>=0;j--)
if(!v[j])
      {b1=(d1*a1+d2*a3)%M;
      b2=(d1*a2+d2*a4)%M;
      b3=(d3*a1+d4*a3)%M;
      b4=(d3*a2+d4*a4)%M;
      a1=b1,a2=b2,a3=b3,a4=b4;
      c1=(d1*d1+d2*d3)%M;
      c2=(d1*d2+d2*d4)%M;
      c3=(d3*d1+d4*d3)%M;
      c4=(d3*d2+d4*d4)%M;
      d1=c1,d2=c2,d3=c3,d4=c4;}
else
      {b1=(d1*a1+d2*a3)%M;
      b2=(d1*a2+d2*a4)%M;
      b3=(d3*a1+d4*a3)%M;
      b4=(d3*a2+d4*a4)%M;
      d1=b1,d2=b2,d3=b3,d4=b4;
      c1=(a1*a1+a2*a3)%M;
      c2=(a1*a2+a2*a4)%M;
      c3=(a3*a1+a4*a3)%M;
      c4=(a3*a2+a4*a4)%M;
      a1=c1,a2=c2,a3=c3,a4=c4;}
printf("%lld",d4%M);
return 0;}