# include <fstream>
# define mod 666013
using namespace std;
ifstream f ("kfib.in");
ofstream g ("kfib.out");
int k;

  struct mat
  {
	  long long int m11,m12,m21,m22;
  }z,a,b;

  mat prod (mat a,mat b)
  {
	  mat c;
	  c.m11=(a.m11*b.m11+a.m12*b.m21)%mod;
	  c.m12=(a.m11*b.m12+a.m12*b.m22)%mod;
	  c.m21=(a.m21*b.m11+a.m22*b.m21)%mod;
	  c.m22=(a.m21*b.m12+a.m22*b.m22)%mod;
	  return c;
  }
  
  mat putere (int p,mat a)
  {
	  if (p==1)
		  return a;
	  else
		  if (p%2==1)
			  return prod (z,putere(p-1,z));
		  else
		  {
			  b=putere (p/2,z);
			  return prod (b,b);
		  }
  }
   
int main ()
{
	f>>k;
	z.m11=0;
	z.m12=z.m21=z.m22=1;
	a=putere (k-1,z);
	g<<a.m22;
	
	
}