#include <stdio.h>
#include <vector>

using namespace std;

typedef long long T;

const T KMAX = 1000000000;
const T MOD = 666013;

T K;

vector<vector<T>> mult(vector<vector<T>> M1, vector<vector<T>> M2) {
   vector<vector<T>> M3(M1.size(), vector<T>(M1[0].size(), 0));

   for (int i = 0; i < int(M1.size()); ++i) {
      for (int j = 0; j < int(M1[0].size()); ++j) {
         for (int k = 0; k < int(M1.size()); ++k) {
            M3[i][j] = (M3[i][j] % MOD + ((M1[i][k] % MOD) * (M2[k][j] % MOD)) % MOD) % MOD;
         }
      }
   }

   return M3;
}

vector<vector<T>> pow(T n, vector<vector<T>> M) {
   if (n == 0) {
      return {{1, 0}, {0, 1}};
   }
   if (n == 1) {
      return M;
   }

   if ((n & 1) == 0) {
      return pow(n / 2, mult(M, M));
   } else {
      return mult(M, pow((n - 1) / 2, mult(M, M)));
   }
}

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

   scanf("%lld", &K);

   vector<vector<T>> base = {{0,1}, {1,1}};
   vector<vector<T>> M = pow(K - 1, base);
   printf("%lld", M[1][1]);

   fclose(stdin);
   fclose(stdout);
   return 0;
}