#include<cstdio>

using namespace std;

const int mod=666013;



void produs(int a[3][3], int b[3][3]){

  int i,j,k,aux[3][3];
  for(i=0;i<3;i++)
    for(j=0;j<3;j++){

      aux[i][j]=0;
      for(k=0;k<3;k++)
        aux[i][j]+=a[i][k]*b[k][j];

    }
  for(i=0;i<3;i++)
    for(j=0;j<3;j++)
      a[i][j]=aux[i][j]%mod;

}

int main(){

  freopen("kfib.in","r",stdin);
  freopen("kfib.out","w",stdout);

  int n,i,j;

  scanf("%d",&n);

  n-=2;

  int p[3][3]={{1,0,0},{0,1,0},{0,0,1}};
  int a[3][3]={{1,1,0},{1,0,0},{0,1,0}};

  while(n!=0){

    if(n%2!=0)
        produs(p,a);
    produs(a,a);
    n/=2;

  }

  printf("%d",(p[0][1]+p[0][0])%mod);

return 0;
}