#include <iostream>

#define MOD 666013

using namespace std;

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

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

long long Fibonacci (int K)
{
    long long FibK, Fib0=0, Fib1=1, Z[2][2];
    if (K==0)
    {
        return Fib0;
    }
    if (K==1)
    {
        return Fib1;
    }
    Z[0][0]=0;
    Z[0][1]=Z[1][0]=Z[1][1]=1;
    LgPow (Z, K-1);
    FibK=(Fib0*Z[0][1]+Fib1*Z[1][1]+MOD)%MOD;
    return FibK;
}

int main()
{
    freopen ("kfib.in", "r", stdin);
    freopen ("kfib.out", "w", stdout);
    int K;
    scanf ("%d", &K);
    printf ("%lld\n", Fibonacci (K));
    return 0;
}