#include<stdio.h>
#define N 1000001
long long k,a1,a2,a3,a4,b1,b2,b3,b4,d1,d2,d3,d4,c1,c2,c3,c4;
int v[N],i=0,j;

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;}
d1=0;
d2=1;
d3=1;
d4=1;
a1=1;
a2=1;
a3=1;
a4=2;
for(j=i-2;j>=0;j--)
     {if(v[j]==0)
                 {b1=(d1*a1+d2*a3)%666013;
                 b2=(d1*a2+d2*a4)%666013;
                 b3=(d3*a1+d4*a3)%666013;
                 b4=(d3*a2+d4*a4)%666013;
                 a1=b1;
                 a2=b2;
                 a3=b3;
                 a4=b4;
                 c1=(d1*d1+d2*d3)%666013;
                 c2=(d1*d2+d2*d4)%666013;
                 c3=(d3*d1+d4*d3)%666013;
                 c4=(d3*d2+d4*d4)%666013;
                 d1=c1;
                 d2=c2;
                 d3=c3;
                 d4=c4;}
     else
                 {b1=(d1*a1+d2*a3)%666013;
                 b2=(d1*a2+d2*a4)%666013;
                 b3=(d3*a1+d4*a3)%666013;
                 b4=(d3*a2+d4*a4)%666013;
                 d1=b1;
                 d2=b2;
                 d3=b3;
                 d4=b4;
                 c1=(a1*a1+a2*a3)%666013;
                 c2=(a1*a2+a2*a4)%666013;
                 c3=(a3*a1+a4*a3)%666013;
                 c4=(a3*a2+a4*a4)%666013;
                 a1=c1;
                 a2=c2;
                 a3=c3;
                 a4=c4;}}
printf("%ld\n",d4%666013);
fclose(stdin);
fclose(stdout);
return 0;}