#include<stdio.h>
#define N 1000001
typedef struct point
{long a,b,c,d;};
long k,i=0,v[N],j,a1,a2,b1,b2,c1,c2,d1,d2;
point p1,p2;

int main()
{freopen("kfib.in","r",stdin);
freopen("kfib.out","w",stdout);
scanf("%ld\n",&k);
k--;
while(k!=0)
     {v[i++]=k%2;
     k/=2;}
p1.a=0;
p1.b=1;
p1.c=1;
p1.d=1;
p2.a=1;
p2.b=1;
p2.c=1;
p2.d=2;
for(j=i-2;j>=0;j--)
if(v[j]==1)
      {a1=p1.a*p2.a+p1.b*p2.c;
      b1=p1.a*p2.b+p1.b*p2.d;
      c1=p1.c*p2.a+p1.d*p2.c;
      d1=p1.c*p2.b+p1.d*p2.d;
      a2=p2.a*p2.a+p2.b*p2.c;
      b2=p2.a*p2.b+p2.b*p2.d;
      c2=p2.c*p2.a+p2.d*p2.c;
      d2=p2.c*p2.b+p2.d*p2.d;
      p1.a=a1;
      p1.b=b1;
      p1.c=c1;
      p1.d=d1;
      p2.a=a2;
      p2.b=b2;
      p2.c=c2;
      p2.d=d2;}
else
      {a2=p1.a*p2.a+p1.b*p2.c;
      b2=p1.a*p2.b+p1.b*p2.d;
      c2=p1.c*p2.a+p1.d*p2.c;
      d2=p1.c*p2.b+p1.d*p2.d;
      a1=p1.a*p1.a+p1.b*p1.c;
      b1=p1.a*p1.b+p1.b*p1.d;
      c1=p1.c*p1.a+p1.d*p1.c;
      d1=p1.c*p1.b+p1.d*p1.d;
      p2.a=a2;
      p2.b=b2;
      p2.c=c2;
      p2.d=d2;
      p1.a=a1;
      p1.b=b1;
      p1.c=c1;
      p1.d=d1;}
printf("%ld\n",p1.d%666013);
fclose(stdin);
fclose(stdout);
return 0;}