#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%666013)*(p2.a%666013))%666013+((p1.b%666013)*(p2.c%666013))%666013)%666013;
      b1=(((p1.a%666013)*(p2.b%666013))%666013+((p1.b%666013)*(p2.d%666013))%666013)%666013;
      c1=(((p1.c%666013)*(p2.a%666013))%666013+((p1.d%666013)*(p2.c%666013))%666013)%666013;
      d1=(((p1.c%666013)*(p2.b%666013))%666013+((p1.d%666013)*(p2.d%666013))%666013)%666013;
      a2=(((p2.a%666013)*(p2.a%666013))%666013+((p2.b%666013)*(p2.c%666013))%666013)%666013;
      b2=(((p2.a%666013)*(p2.b%666013))%666013+((p2.b%666013)*(p2.d%666013))%666013)%666013;
      c2=(((p2.c%666013)*(p2.a%666013))%666013+((p2.d%666013)*(p2.c%666013))%666013)%666013;
      d2=(((p2.c%666013)*(p2.b%666013))%666013+((p2.d%666013)*(p2.d%666013))%666013)%666013;
      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%666013)*(p2.a%666013))%666013+((p1.b%666013)*(p2.c%666013))%666013)%666013;
      b2=(((p1.a%666013)*(p2.b%666013))%666013+((p1.b%666013)*(p2.d%666013))%666013)%666013;
      c2=(((p1.c%666013)*(p2.a%666013))%666013+((p1.d%666013)*(p2.c%666013))%666013)%666013;
      d2=(((p1.c%666013)*(p2.b%666013))%666013+((p1.d%666013)*(p2.d%666013))%666013)%666013;
      a1=(((p1.a%666013)*(p1.a%666013))%666013+((p1.b%666013)*(p1.c%666013))%666013)%666013;
      b1=(((p1.a%666013)*(p1.b%666013))%666013+((p1.b%666013)*(p1.d%666013))%666013)%666013;
      c1=(((p1.c%666013)*(p1.a%666013))%666013+((p1.d%666013)*(p1.c%666013))%666013)%666013;
      d1=(((p1.c%666013)*(p1.b%666013))%666013+((p1.d%666013)*(p1.d%666013))%666013)%666013;
      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;}