#include <iostream>

#define MOD 666013
using namespace std;

int a[2][2];

void product(int a[2][2], int b[2][2]) {
  int i, j, k;
  int c[2][2];

  for ( i = 0; i < 2; i++ ) {
    for ( j = 0; j < 2; j++ ) {
      c[i][j] = 0;
      for ( k = 0; k < 2; k++ ) {
        c[i][j] = (c[i][j] + (long long) a[i][k] * b[k][j] % MOD) % MOD;
      }
    }
  }

  for ( i = 0; i < 2; i++ ) {
    for ( j = 0; j < 2; j++ ) {
      a[i][j] = c[i][j];
    }
  }
}

int rez[2][2];
void lgPut(int n) {
  int i;
  int b[2][2];

  while ( n ) {
    if ( n % 2 == 1 )
      product(rez, a);
    product(a, a);
    n /= 2;
  }
}

int main() {
  FILE *fin, *fout;
  fin = fopen("kfib.in", "r");
  fout = fopen("kfib.out", "w");

  int n;

  fscanf(fin, "%d", &n);

  rez[0][0] = a[0][0] = 0;
  rez[0][1] = rez[1][1] = rez[1][0] = a[0][1] = a[1][1] = a[1][0] = 1;
  lgPut(n - 1);
  fprintf(fout, "%d\n", rez[0][1]);

  fclose(fin);
  fclose(fout);

  return 0;
}