#include <stdio.h>
#include <stdlib.h>
#define DIM 2
#define MOD 666013

int mat[DIM][DIM]={{1, 1}, {1, 0}}, sol[DIM][DIM];

void mymult(int n, int a[][DIM], int b[][DIM], int c[][DIM]){
  int i, j, k;
  for(i=0; i<n; i++)
    for(j=0; j<n; j++){
      c[i][j]=0;
      for(k=0; k<n; k++)
        c[i][j]=(c[i][j]+1LL*a[i][k]*b[k][j])%MOD;
    }
}

void mycopy(int n, int d[][DIM], int s[][DIM]){
  int i, j;
  for(i=0; i<n; i++)
    for(j=0; j<n; j++)
      d[i][j]=s[i][j];
}

void inv(int n, int in[][DIM]){
  int i, j;
  for(i=0; i<n; i++){
    for(j=0; j<n; j++)
      in[i][j]=0;
    in[i][i]=1;
  }
}

void mypow(int n, int expo, int mat[][2], int rez[][2]){
  int aux[DIM][DIM];
  inv(DIM, rez);
  while(expo){
    if(expo&1){
      mymult(DIM, mat, rez, aux);
      mycopy(DIM, rez, aux);
    }
    mymult(DIM, mat, mat, aux);
    mycopy(DIM, mat, aux);
    expo>>=1;
  }
}

int main()
{
    FILE *fin, *fout;
    int n;
    fin=fopen("kfib.in", "r");
    fscanf(fin, "%d", &n);
    fclose(fin);
    mypow(DIM, n-1, mat, sol);
    fout=fopen("kfib.out", "w");
    fprintf(fout, "%d\n", sol[0][0]);
    fclose(fout);
    return 0;
}