#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 solve(int n) {
  int log[2][2] = {{1, 0}, {0, 1}}; 
  int use[2][2] = {{0, 1}, {1, 1}};
  int temp[2][2];
  int last[2][2] = {{1, 1}, {0, 0}};


  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(temp));
  }

  multiply(last, log, temp);
  g<<temp[0][1];
}

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