#include <stdio.h>
#define mod 666013
typedef long long int i64;
class M
{private:
 i64 a,b,c,d;
 
 public:
 M()
 {a=c=1;
  b=d=0;
 }
 
 M(int x,int y,int z,int t)
 {a=x;b=y;c=z;d=t;
 }
 
 M operator+(M m2)
 {M r;
  r.a=(a+m2.a)%mod;
  r.b=(a+m2.b)%mod;
  r.c=(a+m2.c)%mod;
  r.d=(a+m2.d)%mod;
  return r;
 }

 M operator*(M m2)
 {M r;
  r.a=(a*m2.a+b*m2.c)%mod;
  r.b=(a*m2.b+b*m2.d)%mod;
  r.c=(c*m2.a+d*m2.c)%mod;
  r.d=(c*m2.b+d*m2.d)%mod;
  return r;
 }

 int suma()
 {return (int)a;
 }

 static M fib()
 {M r;
  r.a=r.b=r.c=1;
  r.d=0;
  return r;
 }
};

int main ()
{freopen("kfib.in","r",stdin);
 freopen("kfib.out","w",stdout);
 unsigned k,r,i;
 M p,s;
 scanf("%d",&k);
 
 if(k==0||k==1)
 {printf("%d",k);
  return 0;
 }
  k-=2;
 
 for (i=1,p=M::fib();i<=k;i<<=1)
 {if(i&k)
  {s=p*s;
  }
  p=p*p;
 }
 
 printf("%d",s.suma());
 
 return 0;
}