#include<fstream>  
using namespace std;  
ifstream f("kfib.in"); 
ofstream g("kfib.out"); 
long long a,b,c,n,i;
int main(){
	f>>n;
	n=n%(666013*2+2);
	a=1;b=1;
	for (i=3;i<=n;i++){
		c=(a+b)%666013;
		a=b;
		b=c;
	}
	g<<b<<"\n";
	return 0;
}