#include <bits/stdc++.h>

using namespace std;

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

int ans[3][3], mat[3][3], n;
const int MOD=666013;

void inmultire(int a[3][3], int b[3][3], int c[3][3]){
  int aux[3][3]={0};
  for(int i=1; i<=2; i++)
  {
    for(int j=1; j<=2; j++)
    {
      for(int k=1; k<=2; k++)
      {
        aux[i][j]=(aux[i][j]+1LL*a[i][k]*b[k][j]%MOD)%MOD;
      }
    }
  }
  for(int i=1; i<=2; i++)
  {
    for(int j=1; j<=2; j++)
    {
      c[i][j]=aux[i][j];
    }
  }
}

void exp(int x)
{
  while(x)
  {
    if(x%2)
    {
      inmultire(ans, mat, ans);
    }
    inmultire(mat, mat, mat);
    x/=2;
  }
}

int main()
{
    in>>n;
    if(n==0)
    {
      cout<<"0";
    }
    else if(n==1 || n==2)
    {
      cout<<"1";
    }
    else if(n==3)
    {
      cout<<"2";
    }
    else
    {
      ans[1][1]=ans[2][2]=mat[1][2]=mat[2][2]=mat[2][1]=1;
      exp(n-2);
      out<<(ans[2][1]+ans[2][2])%MOD;
    }
    return 0;
}