#include <bits/stdc++.h>
#define int long long

using namespace std;

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

const int MOD = 666013;

class Matrix {
  private :
    int mat[2][2];
    int n, m;
  public :
    Matrix(int _x, int _y, int _z, int _w, int _q1, int _q2){
      mat[0][0] = _x;
      mat[0][1]= _y;
      mat[1][0] = _z;
      mat[1][1] = _w;
      n = _q1;
      m = _q2;
    }

    Matrix operator* (const Matrix &shit) {
      Matrix ans(0, 0, 0, 0, n, 2);
      for( int i = 0; i < n; ++i )
        for( int j = 0; j < m; ++j )
          for( int k = 0; k < 2; ++k )
            ans.mat[i][j] = (ans.mat[i][j] + (mat[i][k] * shit.mat[k][j]) % MOD) % MOD;
      return ans;
    }

    int getResult() {
      return mat[0][1];
    }
};

int lgput( Matrix a, int b ){
  Matrix p(1, 0, 0, 1, 1, 2);
  while( b > 0 ){
    if( b % 2 == 1 )
      p = p * a;
    a = a * a;
    b /= 2;
  }
  return p.getResult();
}

signed main() {
  int n;
  fin >> n;
  Matrix a(0, 1, 1, 1, 2, 2);
  fout << lgput(a, n);
  return 0;
}