#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ifstream fin( "kfib.in" );
ofstream fout( "kfib.out" );

const int MOD = 666013;

struct Matrix {
  int val[2][2];

  Matrix operator * ( const Matrix &a ) {
	Matrix b = {{{0, 0}, {0, 0}}};
	
	for ( int i = 0; i < 2; ++i ) 
      for ( int j = 0; j < 2; ++j ) 
		for ( int k = 0; k < 2; ++k ) 
		  b.val[i][j] = (b.val[i][j] + (ll)this->val[i][k] * a.val[k][j]) % MOD;
   
    return b;
  }
};

Matrix lgpow( Matrix a, int n ) {
  Matrix p = {{{1, 0}, {0, 1}}};
  for ( ; n; n >>= 1 ) {
	if ( n & 1 ) p = p * a;
	a = a * a;
  }
  return p;
}

int main() {
  ios_base::sync_with_stdio(0);
  fin.tie(0);
  int n;

  fin >> n; 
  Matrix base = {{{1, 1}, {1, 0}}};
  base = lgpow(base, n);
  fout << base.val[0][1];
  fin.close();
  fout.close();
  return 0;
}