#include <fstream>
using namespace std;

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

int const mod=666013;
int a[3][3], p[3][3];
void produs (int a[3][3], int b[3][3])
{
  int i, j, k;
  int aux[3][3];
  for (i=0; i<3; i++)
    for (j=0; j<3; j++)
    {
      aux[i][j]=0;
      for (k=0; k<3; k++)
      {
        aux[i][j]+=((long long)a[i][k]*b[k][j]) % mod;
        aux[i][j]%=mod;

      }

    }
  for (i=0; i<3; i++)
    for (j=0; j<3; j++)
      a[i][j]=aux[i][j];

}
int main()
{
    int n, k;
    in>>n;
    p[0][0]=p[1][1]=p[2][2]=1;
    a[0][0]=a[0][1]=a[1][0]=a[2][1]=1;
    n-=2;
    while (n!=0)
    {
      if(n%2!=0)
        produs (p, a);
      produs (a, a);
      n/=2;
    }
    /*
    for (int i=0; i<3; i++)
    {
      for (int j=0; j<3; j++)
        out<<p[i][j]<<" ";
      out<<"\n";
    }
    */
    out<<(p[0][0]+p[0][1])%mod;

    return 0;
}