#include <bits/stdc++.h>

#define N 50005
#define oo 0x3f3f3f3f
#define mod 666013

using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
int n;

void multiply(int a[2][2], int b[2][2], int c[2][2]) {
  for(int i = 0;i < 2;++i) {
    for(int j = 0;j < 2;++j) {
      c[i][j] = 0;
      for(int k = 0;k < 2;++k) {
        c[i][j] = (long long)(c[i][j] + 1LL * a[i][k] * b[k][j]) % mod;
      }
    }
  }
}

void copy(int a[2][2], int b[2][2]) {
  for(int i = 0;i < 2;++i) {
    for(int j = 0;j < 2;++j) {
      b[i][j] = a[i][j];
    }
  }
}

void solve(int n) {
  int rez[2][2] = {{1, 1}, {0, 0}};
  int use[2][2] = {{0, 1}, {1, 1}};
  int temp[2][2];
  int log[2][2] = {{1, 0}, {0, 1}};

  for(int i = 0;(1 << i) <= n;++i) {
    if((1 << i) & n) {
      multiply(log, use, temp);
      memcpy(log, temp, sizeof(log));
    }

    multiply(use, use, temp);
    memcpy(use, temp, sizeof(use));
  }
  
  multiply(rez, log, temp);
  g<<temp[0][0]<<'\n';
}

int main() {
  f>>n;
  solve(n - 1);
  return 0;
}