#include <fstream>
#include <cstring>
using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

const int MOD = 666013;
int K;
int Z[5][5],Sol[5][5];

void Multiply(int A[5][5],int B[5][5])
{
  int C[5][5];
  for(int i = 1; i <= 2; ++i)
    for(int j = 1; j <= 2; ++j)
      {
      long long S = 0;
      for(int k = 1; k <= 2; ++k)
        S += 1LL*A[i][k]*B[k][j];
      C[i][j] = S % MOD;
      }
  memcpy(A,C,sizeof(C));
}

int main()
{
    fin>>K;
    Z[1][2] = Z[2][1] = Z[2][2] = 1;
    Sol[1][2] = 1;
    while(K)
    {
      if(K&1)
        {
          Multiply(Sol,Z);
        }
      Multiply(Z,Z);
      K = K / 2;
    }

    fout<<Sol[1][1]<<"\n";
    return 0;
}