#include <iostream>
#include <fstream>
 
using namespace std;
 
ifstream fin ("kfib.in");
ofstream fout ("kfib.out");
 
const int mod = 666013;
 
void inmultire_matrice (long long mat[2][2], long long a[2][2])
{
  int aux[2][2];
  aux[0][0] = (mat[0][0] % mod * a[0][0] % mod) % mod + (mat[0][1] % mod * a[1][0] % mod) % mod;
  aux[0][1] = (mat[0][0] % mod * a[0][1] % mod) % mod + (mat[0][1] % mod * a[1][1] % mod) % mod;
  aux[1][0] = (mat[1][0] % mod * a[0][0] % mod) % mod + (mat[1][1] % mod * a[1][0] % mod) % mod;
  aux[1][1] = (mat[1][0] % mod * a[0][1] % mod) % mod + (mat[1][1] % mod * a[1][1] % mod) % mod;
  for (int i = 0; i < 2; i++)
    {
      for (int j = 0; j < 2; j++)
        mat[i][j] = aux[i][j] % mod;
    } 
}
 
int main()
{
  long long mat[2][2] = {{1, 0}, {0 ,1}}, a[2][2]= {{0, 1}, {1, 1}}, n, i, j; 
  fin >> n;
  if (n == 0)
    cout << 0;
  if (n == 1)
    cout << 1;
  else
  {
    int b = n - 1;
    while (b)
    {
        if (b % 2 == 1)
          inmultire_matrice (mat, a);
        inmultire_matrice (a, a);
        b /= 2;
    }
    fout << mat[1][1];
  }
  
  return 0;
}