#ifdef EZ
   #include "./ez/ez.h"
#else
   #include <bits/stdc++.h>
#endif
#define mp make_pair
#define mt make_tuple
#define ll long long
#define pb push_back
#define fi first
#define se second
using namespace std;
const string FILE_NAME = "kfib";
ifstream fin (FILE_NAME + ".in");
ofstream fout (FILE_NAME + ".out");

const int MOD = 666013;

struct mat2x2 {
   ll v[2][2];

   mat2x2()
   {
      v[0][0] = v[0][1] = v[1][0] = v[1][1] = 0;
   }
};

mat2x2 inmultire(mat2x2 a, mat2x2 b)
{
   mat2x2 c;

   for (int i = 0; i < 2; ++i)
      for (int j = 0; j < 2; ++j)
      {
         for (int k = 0; k < 2; ++k)
            c.v[i][j] += a.v[i][k] * b.v[k][j];
         c.v[i][j] %= MOD;
      }
   
   return c;
}


int main()
{
   int k;
   fin >> k;

   if (k == 0)
      fout << 0,  exit(0);
   
   mat2x2 a, ans;
   a.v[0][0] = a.v[0][1] = a.v[1][0] = 1;
   ans.v[0][0] = ans.v[1][1] = 1;

   for (int b = k-1; b; b >>= 1)
   {
      if (b & 1)
         ans = inmultire(ans, a);
      a = inmultire(a, a);
   }

   fout << ans.v[0][0];
}