#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

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

const int MOD=666013;
int Z[3][3],Sol[3][3],k;

void mmat(int A[3][3],int B[3][3])
{
    int C[3][3];
   for(int i=1;i<=2;i++)
    for(int j=1;j<=2;j++)
      {
      long long S=0;
      for(int k=1;k<=2;k++)
        S+=1LL*A[i][k]*B[k][j];
      C[i][j]=S%MOD;
      }
   memcpy(A,C,sizeof(C));
}

int main()
{
    fin>>k;

    k=k-1;
    Sol[1][1]=Sol[2][2]=1;
    Z[1][2]=Z[2][1]=Z[2][2]=1;

    while(k)
    {

        if(k%2==1)
        {
          mmat(Sol,Z);
        }
        mmat(Z,Z);
        k=k/2;
    }

    fout<<Sol[2][2];

    return 0;
}