#include <fstream>

#define mod 666013

using namespace std;

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

int p;
long long a[3][3],aa[3][3],b[3][3];

inline void putere()
{
    while (p)
     {
         if (p%2)
          {
              aa[1][1]=a[1][1]*b[1][1]+a[1][2]*b[2][1];
              aa[1][2]=a[1][1]*b[1][2]+a[1][2]*b[2][2];
              aa[2][1]=a[2][1]*b[1][1]+a[2][2]*b[2][1];
              aa[2][2]=a[2][1]*b[1][2]+a[2][2]*b[2][2];

              b[1][1]=aa[1][1]%mod;
              b[1][2]=aa[1][2]%mod;
              b[2][1]=aa[2][1]%mod;
              b[2][2]=aa[2][2]%mod;

              p--;
          }
         else
          {
              aa[1][1]=a[1][1]*a[1][1]+a[1][2]*a[2][1];
              aa[1][2]=(a[1][1]+a[2][2])*a[1][2];
              aa[2][1]=(a[1][1]+a[2][2])*a[2][1];
              aa[2][2]=a[2][2]*a[2][2]+a[1][2]*a[2][1];

              a[1][1]=aa[1][1]%mod;
              a[1][2]=aa[1][2]%mod;
              a[2][1]=aa[2][1]%mod;
              a[2][2]=aa[2][2]%mod;

              p/=2;
          }


     }
}

int main()
{
   f>>p;

   a[1][2]=a[2][1]=a[2][2]=1;
   b[1][1]=b[2][2]=1;

   putere();

   g<<b[2][1];

   f.close();
   g.close();
}