#include <iostream>
#include <fstream>
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
unsigned long long M[3][3],I[3][3],n;

void update()
{
    int i,j;
    unsigned long long aux[3][3];
    for (i=1;i<=2;i++)
    {
        for (j=1;j<=2;j++)
        {
            aux[i][j]=I[i][1]*M[1][j]+I[i][2]*M[2][j];
            aux[i][j]%=666013;
        }
    }
    for (i=1;i<=2;i++)
    {
        for (j=1;j<=2;j++) I[i][j]=aux[i][j];
    }
}

void pow()
{
   int i,j;
    unsigned long long aux[3][3];
    for (i=1;i<=2;i++)
    {
        for (j=1;j<=2;j++)
        {
            aux[i][j]=M[i][1]*M[1][j]+M[i][2]*M[2][j];
            aux[i][j]%=666013;
        }
    }
    for (i=1;i<=2;i++)
    {
        for (j=1;j<=2;j++) M[i][j]=aux[i][j];
    }
}


int main()
{
    M[1][1]=0;
    M[1][2]=1;
    M[2][1]=1;
    M[2][2]=1;
    I[1][1]=1;
    I[1][2]=0;
    I[2][1]=0;
    I[2][2]=1;

   f>>n;
   n--;
if (n==0) g<<1;
if (n==-1) g<<0;
if (n>=1)
{
while (n)
{
    if (n%2==1) update();
    n/=2;
    pow();
}
g<<I[2][2];

}
    return 0;
}