#include <algorithm>
using namespace std;

#define MOD 666013
#define DIM 5

long long a[DIM][DIM],rez[DIM][DIM];
int n,p;

inline void mult (long long a[DIM][DIM],long long b[DIM][DIM])
{
    long long c[DIM][DIM];
    int i,j,k;

    memset (c,0,sizeof (c));
    for (i=1; i<=2; ++i)
        for (j=1; j<=2; ++j)
            for (k=1; k<=2; ++k)
                c[i][j]=(c[i][j]+a[i][k]*b[k][j])%MOD;
    memcpy (a,c,sizeof (c));
}

void solve ()
{
    int i;

    for (i=1; i<=2; ++i)
        a[i][3-i]=rez[i][i]=1;
    a[2][2]=1;
    for (p=n; p; p>>=1)
    {
        if (p&1)
            mult (rez,a);
        mult (a,a);
    }
    printf ("%lld",rez[1][2]);
}

int main ()
{
    freopen ("kfib.in","r",stdin);
    freopen ("kfib.out","w",stdout);

    scanf ("%d",&n);
    solve ();

    return 0;
}