#include <bits/stdc++.h>
#define mod 666013 

using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
int n, a[2][2], b[2][2], c[2][2], I[2][2];

void inmult(int x[][2], int y[][2], int z[][2])
{
    for(int i = 0;i < 2;++i)
      for(int j = 0;j < 2;++j)
        {
          z[i][j] = 0;
          for(int k = 0;k < 2;++k)
            z[i][j] = (long long)(z[i][j] + 1LL * x[i][k] * y[k][j]) % mod;
        }
}

void lgpower(int put)
{
  for(int i = 0;i < 32;++i)
    {
      if(put & (1 << i))
        {
          inmult(I, b, c);
          memcpy(I, c, sizeof(I));
        }
      inmult(b, b, c);
      memcpy(b, c, sizeof(b));
    }
}

void Solve()
{
  f>>n;
  a[0][0] = a[0][1] = 1;
  b[0][0] = b[1][0] = b[0][1] = 1;
  I[0][0] = I[1][1] = 1;
  lgpower(n - 1);
  inmult(I, a, c);
  g<<c[0][0];
}

int main()
{
  Solve();
  return 0;
}