#include<stdio.h>
#define dim 666013

unsigned long long int a,b,c,d,p,a1,i,b1,c1,d1;
void multi(unsigned long long int &a,unsigned long long int &b,
		   unsigned long long int &c,unsigned long long int &d,
		   unsigned long long int a1,unsigned long long int b1,
		   unsigned long long int c1,unsigned long long int d1){
unsigned long long int A,B,C,D;

A = a * a1 + b * c1;
B = a * b1 + b * d1;
C = c * a1 + d * c1;
D = c * b1 + d * d1;

if( A > dim) A%=dim;
if( B > dim) B%=dim;
if( C > dim) C%=dim;
if( D > dim) D%=dim;

a = A;
b = B;
c = C;
d = D;

}
int main(){
freopen("kfib.in","r",stdin);
freopen("kfib.out","w",stdout);
scanf("%lld",&p);
p--;
a= 0;
b = c = d  = 1;
a1 = d1 =1;
b1 = c1 = 0;
while(p)
	{if(p%2)
		multi(a1,b1,c1,d1,a,b,c,d);
	multi(a,b,c,d,a,b,c,d);
	p=p>>1;
	}
printf("%lld",d1);
return 0;}