#include <stdio.h>
#include <cstdlib>
#define mod 666013
using namespace std;

struct matrice
{
  long long a,b,c,d;
}I2,A;
 long long n;
FILE *f1=fopen("kfib.in","r"),*f2=fopen("kfib.out","w");

matrice inmulteste(matrice A,matrice B)
{
      matrice C;
      C.a=(A.a*B.a%mod)+(A.b*B.c%mod);
      C.b=(A.a*B.b%mod)+(A.b*B.d%mod);
      C.c=(A.c*B.a%mod)+(A.d*B.c%mod);
      C.d=(A.c*B.b%mod)+(A.d*B.d%mod);

      return C;
}
matrice exp(matrice X,long long p)
{
    if(p==0)return I2;
    if(p==1)return X;
    if(p%2==0) return exp(inmulteste(X,X),p/2);
    if(p%2!=0) return inmulteste(exp(inmulteste(X,X),p/2),X);
}
int main()
{
    A.b=A.c=A.d=1;
    I2.a=I2.d=1;
  fscanf(f1,"%lld",&n);

  A=exp(A,n-1);

  fprintf(f2,"%lld",A.d%mod);
  return 0;
}

//Our greatest weakness lies in giving up. The most certain way to succeed is always to try just one more time.