#include <fstream>
#define MOD 666013

using namespace std;

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

int N, i, j;
long long mat[3][3];
long long v[3][3];
long long x[3][3];

void mult1()
{
    int i, j;
    for (i=1; i<=2; i++)
      for (j=1; j<=2; j++)
        x[i][j]=v[i][1]*mat[1][j]+v[i][2]*mat[2][j];
    for (i=1; i<=2; i++)
      for (j=1; j<=2; j++)
        v[i][j]=x[i][j] % MOD;
}

void mult2()
{
    int i, j;
    for (i=1; i<=2; i++)
      for (j=1; j<=2; j++)
        x[i][j]=mat[i][1]*mat[1][j]+mat[i][2]*mat[2][j];
    for (i=1; i<=2; i++)
      for (j=1; j<=2; j++)
        mat[i][j]=x[i][j] % MOD;
}

int main()
{
    fin >> N;
    if (N==0)
      fout << 0;
    if (N==1)
      fout << 1;
    if (N>1)
    {
        N-=2;
        mat[1][1]=mat[1][2]=mat[2][1]=1;
        mat[2][2]=0;
        v[1][1]=v[1][2]=v[2][1]=1;
        v[2][2]=0;
        while (N!=0)
        {
            if (N % 2==1)
            {
                mult1();
                N--;
            }
            else
            {
                mult2();
                N/=2;
            }
        }
        fout << v[1][1] << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}