#include<fstream>
#include<iostream>
#include<vector>
using namespace std;
#define mod 666013

void matrix_pow(long long a[2][2]) {
  int c[2][2];
  c[0][0] = ((a[0][0] * a[0][0]) + (a[0][1] * a[1][0])) % mod;
  c[0][1] = ((a[0][0] * a[0][1]) + (a[0][1] * a[1][1])) % mod;
  c[1][0] = ((a[1][0] * a[0][0]) + (a[1][1] * a[1][0])) % mod;
  c[1][1] = ((a[1][0] * a[0][1]) + (a[1][1] * a[1][1])) % mod;
  
  a[0][0] = c[0][0]; a[0][1] = c[0][1];
  a[1][0] = c[1][0]; a[1][1] = c[1][1];
}

void matrix_mult(long long a[2][2], long long b[2][2]) {
  int c[2][2];
  c[0][0] = ((a[0][0] * b[0][0]) + (a[0][1] * b[1][0])) % mod;
  c[0][1] = ((a[0][0] * b[0][1]) + (a[0][1] * b[1][1])) % mod;
  c[1][0] = ((a[1][0] * b[0][0]) + (a[1][1] * b[1][0])) % mod;
  c[1][1] = ((a[1][0] * b[0][1]) + (a[1][1] * b[1][1])) % mod;

  a[0][0] = c[0][0]; a[0][1] = c[0][1];
  a[1][0] = c[1][0]; a[1][1] = c[1][1];  
}

void print_mat(long long a[2][2]) {
  cout << a[0][0] << ' ' << a[0][1] << '\n';
  cout << a[1][0] << ' ' << a[1][1] << '\n';
  cout << "----------------------\n";
}

int main() {
  ifstream in("kfib.in");
  ofstream out("kfib.out");

  long long N; in >> N;
  long long a[2][2] = {{1,1}, 
		       {1,0}};
  long long mat[2][2] = {{1,0}, 
			 {0,1}};
  
  for(int i = 0; (1 << i) <= N; i++) {
    if(((1<<i) & N) != 0) {
      matrix_mult(mat, a);
    }
    matrix_pow(a);
  }
  
  out << mat[0][1] << '\n';
  return 0;
}