#include<fstream>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
int main()
{
	int k,t1,t2,i,z,mod=666013;
  fin>>k;
	k%=mod*2+2;
  t1=1; t2=1; 
  for(i=3;i<=k;i++)
  {
    z=(t1+t2)%mod;
    t1=t2;
    t2=z;
	}
	
  fout<<t2;
  fin.close();
  fout.close();
  
	return 0;
}