#include<fstream>
 
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
const long MOD=666013;
int main()
{
 
    long k;
    fin>>k;
    k=k%(666013*2+2);    
    if(k==0){
		fout<<0;
		return 0;
    }
    if(k<=2){
		fout<<1;
		return 0;
    }
	long x=1,y=1,z;
    for(long i=3;i<=k;i++){
		z=(x+y)%666013;
		x=y;
		y=z;
    }
    
    fout<<z<<endl;
}