#include <bits/stdc++.h>
using namespace std;
const int MOD = 666013;
void mltp(int a[2][2], int b[2][2])
{
   int x = 1LL * a[0][0] * b[0][0] % MOD + 1LL * a[0][1] * b[1][0] % MOD;
   int y = 1LL * a[0][0] * b[0][1] % MOD + 1LL * a[0][1] * b[1][1] % MOD;
   int z = 1LL * a[1][0] * b[0][0] % MOD + 1LL * a[1][1] * b[1][0] % MOD;
   int u = 1LL * a[1][0] * b[0][1] % MOD + 1LL * a[1][1] * b[1][1] % MOD;
   a[0][0] = x % MOD;
   a[0][1] = y % MOD;
   a[1][0] = z % MOD;
   a[1][1] = u % MOD;
}

int pow(int f[2][2], int x)
{
   int ans[2][2];
   memcpy(ans, f, 16);
   x--;

   while (x)
   {
      if (x & 1)
      {
         mltp(ans, f);
         x -= 1;
      }
      else
      {
         mltp(f, f);
         x >>= 1;
      }
   }

   return ans[0][1];
}

int fib(int n)
{
   int f[2][2] = {{1,1}, {1,0}};
   return pow(f, n);
}

int main(){
  //freopen ("file.in", "r", stdin);
  ios_base::sync_with_stdio(false), cin.tie(NULL);
   int n;
   cin >> n;
   cout << fib(n);
}