#include <fstream>

using namespace std;
const int MOD = 666013;
void  produs(int p[2][2],int a[2][2], int b[2][2]){
  int aux[2][2];
  for(int i = 0; i < 2; i++){
    for(int k = 0; k < 2; k++){
      aux[i][k] = 0;
      for(int j = 0; j < 2; j++){
        aux[i][k] += ((long long)a[i][j] * b[j][k]) % MOD;
        aux[i][k] %= MOD;
      }
    }
  }
  for(int i = 0; i < 2; i++){
    for(int k = 0; k < 2; k++){
      p[i][k] = aux[i][k];
    }
  }
}
int main()
{
    ifstream in("kfib.in");
    ofstream out("kfib.out");
    int k;
    in >> k;
    k -= 2;
    int a[2][2]= {{1, 1}, {1, 0}};
    int p[2][2]= {{1, 1}, {1, 0}};
    while(k > 0){
      if( k % 2 != 0)
        produs(p, p, a);
      produs(a, a, a);
      k /= 2;
    }
    out << p[0][0];
    return 0;
}