#include <iostream>

#define MOD 666013

using namespace std;

long long Z[2][2], K, F, F0=0, F1=1;

void Read ()
{
    freopen ("kfib.in", "r", stdin);
    scanf ("%d", &K);
    Z[0][0]=0;
    Z[0][1]=Z[1][0]=Z[1][1]=1;
}

void Print ()
{
    freopen ("kfib.out", "w", stdout);
    printf ("%d\n", F);
}

void Multiply (long long M1[2][2], long long M2[2][2], long long S[2][2])
{
    long long P[2][2];
    for (long long i=0; i<2; ++i)
    {
        for (long long j=0; j<2; ++j)
        {
            P[i][j]=0;
            for (long long k=0; k<2; ++k)
            {
                P[i][j]+=(M1[i][k]*M2[k][j]);
            }
        }
    }
    for (long long i=0; i<2; ++i)
    {
        for (long long j=0; j<2; ++j)
        {
            S[i][j]=P[i][j]%MOD;
        }
    }
}

void LogPow (long long M[2][2], long long P)
{
    long long S[2][2];
    for (long long i=0; i<2; ++i)
    {
        for (long long j=0; j<2; ++j)
        {
            S[i][j]=0;
            if (i==j)
            {
                S[i][j]=1;
            }
        }
    }
    while (P>0)
    {
        if (P%2==0)
        {
            Multiply (M, M, M);
            P/=2;
        }
        else
        {
            Multiply (M, S, S);
            --P;
        }
    }
    for (long long i=0; i<2; ++i)
    {
        for (long long j=0; j<2; ++j)
        {
            Z[i][j]=S[i][j]%MOD;
        }
    }
}

int main()
{
    Read ();
    if (K>0)
    {
        LogPow (Z, K-1);
    }
    F=F0*Z[0][1]+F1*Z[1][1];
    F%=MOD;
    if (K==0)
    {
        F=F0;
    }
    if (K==1)
    {
        F=F1;
    }
    Print ();
    return 0;
}