#include <fstream>
#include <cstring>
#define X 666013
#define D 3

using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");

int k,Z[D][D];

void Multiplication(int A[][D], int B[][D], int C[][D])
{
    int aux[D][D];
    memset(aux,0,sizeof(aux));
    for (int i=1; i<=2; ++i)
        for (int j=1; j<=2; ++j)
        {
            unsigned long long S=0;
            for (int k=1; k<=2; ++k) S+=1LL*A[i][k]*B[k][j];
            aux[i][j]=1LL*S%X;
        }
    memcpy(C,aux,sizeof(aux));
}

void MatrixPower(int Z[][D],int k)
{
    int aux[D][D];
    memset(aux,0,sizeof(aux));
    for (int i=1; i<D; ++i) aux[i][i]=1;
    while (k>1)
    {
        if (k%2==0)
        {
            Multiplication(Z,Z,Z);
            k=k/2;
        }
        else
        {
            Multiplication(aux,Z,aux);
            --k;
        }
    }
    Multiplication(Z,aux,Z);
}

int main()
{
    f>>k;
    Z[1][1]=0; Z[1][2]=1;
    Z[2][1]=1; Z[2][2]=1;
    MatrixPower(Z,k-1);
    g<<Z[2][2]<<'\n';
    f.close();
    g.close();
    return 0;
}