using namespace std;

#include<iostream>
#include<fstream>
#define mod 666013
ofstream fout("kfib.out");
long long N;
int a[3][3],z[3][3],s[3][3];
void inm(int A[3][3],int B[3][3],int l1,int c2,int sim)
{   int C[3][3];
    int i,j,k;
    for(i=1;i<=l1;i++)
      for(j=1;j<=c2;j++)
      {
            C[i][j]=0;
          for(k=1;k<=sim;k++)
          {

              C[i][j]=(C[i][j]+(1LL*A[i][k]*B[k][j])%mod)%mod;
          }
      }
      for(i=1;i<=l1;i++)
        for(j=1;j<=c2;j++)
          A[i][j]=C[i][j];
}

void cit()
{
    ifstream fin("kfib.in");

    fin>>N;
    a[1][1]=0;a[1][2]=1;

    z[1][1]=0;z[1][2]=1;
    z[2][1]=1;z[2][2]=1;

    s[1][1]=1;s[1][2]=0;
    s[2][1]=0;s[2][2]=1;
    int i;
    for(i=1;i<=N-1;i*=2)
    {
        if(i & (N-1))
         {
             inm(s,z,2,2,2);
         }
         inm(z,z,2,2,2);
    }
    inm(a,s,1,2,2);
    fout<<a[1][2]<<"\n";
    fin.close();

}

int main()
{
    cit();


    fout.close();
    return 0;
}