#include <stdio.h>
#include <stdlib.h>

#define MOD 666013

int mat[2][2];

void logput(int p){
  int l, c, i, aux;
  int actual[2][2], secact[2][2];
  if(p != 1){
    for(l = 0; l < 2; l++){
      for(c = 0; c < 2; c++){
        actual[l][c] = mat[l][c];
      }
    }
    for(l = 0; l < 2; l++){
      for(c = 0; c < 2; c++){
        aux = 0;
        for(i = 0; i < 2; i++){
          aux = (aux + ((long long)actual[i][c] * actual[l][i]) % MOD) % MOD;
        }
        secact[l][c] = aux;
      }
    }
    for(l = 0; l < 2; l++){
      for(c = 0; c < 2; c++){
        mat[l][c] = secact[l][c];
      }
    }
    logput(p / 2);
    for(l = 0; l < 2; l++){
      for(c = 0; c < 2; c++){
        secact[l][c] = mat[l][c];
      }
    }
    if((p % 2) == 1){
      for(l = 0; l < 2; l++){
        for(c = 0; c < 2; c++){
          aux = 0;
          for(i = 0; i < 2; i++){
            aux = (aux + ((long long)secact[i][c] * actual[l][i]) % MOD) % MOD;
          }
          mat[l][c] = aux;
        }
      }
    }
  }
}

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