#include <cstdio>
#include <cstring>
const int NMAX = 3;
const int MOD = 666013;
int k, G[NMAX][NMAX], st[NMAX][NMAX];

void mul(int A[NMAX][NMAX], int B[NMAX][NMAX], int n) {
  int res[NMAX][NMAX];
  memset(res, 0, sizeof(res));
  for (int i = 1; i <= n; i++)
    res[i][i] = 1;
    
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      long long curr = 0;
      for (int k = 1; k <= n; k++) {
        curr += 1LL * A[i][k] * B[k][j];
      }
      res[i][j] = curr % MOD;
    }
  memcpy(A, res, sizeof(res));
}

void lgput(int A[NMAX][NMAX], int n, int exp) {
  int res[NMAX][NMAX];
  memset(res, 0, sizeof(res));
  for (int i = 1; i <= n; i++)
    res[i][i] = 1;
    
  while (exp) {
    if (exp & 1) {
      mul(res, A, n);
    }
    mul(A, A, n);
    exp >>= 1;
  }
  
  memcpy(A, res, sizeof(res));
}

int main() {
  freopen("kfib.in", "r", stdin);
  freopen("kfib.out", "w", stdout);
  
  scanf("%d", &k);
  if (k == 0) {
    printf("0\n");
    return 0;
  }
  
  st[2][1] = 1;
  G[1][2] = G[2][1] = G[2][2] = 1;
  lgput(G, 2, k - 1);
  mul(G, st, 2);
  
  printf("%d\n", G[2][1]);
  return 0;
}