#include <fstream>
#include <iostream>
using namespace std;
ifstream fi("kfib.in");
ofstream fo("kfib.out");
long unsigned long z[3][3];
long unsigned long t[3][3];
long unsigned long a[3][3];
int n,p=0;
int putere(int x)
{
    if (x>1)
    {
        putere(x/2);
        //ridic la patrat matricea z
          a[1][1]=z[1][1]*z[1][1]+z[1][2]*z[2][1];
          a[1][2]=z[1][1]*z[1][2]+z[1][2]*z[2][2];
          a[2][1]=z[2][1]*z[1][1]+z[2][2]*z[2][1];
          a[2][2]=z[2][1]*z[1][2]+z[2][2]*z[2][2];
          z[1][1]=a[1][1]%666013;
          z[1][2]=a[1][2]%666013;
          z[2][1]=a[2][1]%666013;
          z[2][2]=a[2][2]%666013;
        //daca ramine rest atunci inmultesc cu matricea constanta
        if (x % 2)
            {
                  a[1][1]=z[1][1]*t[1][1]+z[1][2]*t[2][1];
                  a[1][2]=z[1][1]*t[1][2]+z[1][2]*t[2][2];
                  a[2][1]=z[2][1]*t[1][1]+z[2][2]*t[2][1];
                  a[2][2]=z[2][1]*t[1][2]+z[2][2]*t[2][2];
                  z[1][1]=a[1][1]%666013;
                  z[1][2]=a[1][2]%666013;
                  z[2][1]=a[2][1]%666013;
                  z[2][2]=a[2][2]%666013;
            }
        if (x == n+1)
              {

                  return z[1][1];
              }

    }
}
int main()
{
    z[1][1]=t[1][1]=0;
    z[1][2]=t[1][2]=1;
    z[2][1]=t[2][1]=1;
    z[2][2]=t[2][2]=1;
    fi>>n;
    fo<<putere(n+1)<<"\n";
}