#include <algorithm>
using namespace std;

#define MOD 666013
#define DIM 5

int rez[DIM][DIM],a[DIM][DIM],sol[DIM][DIM];
int k;

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

    for (i=1; i<=n; ++i)
        for (j=1; j<=p; ++j)
        {
            c[i][j]=0;
            for (k=1; k<=m; ++k)
                c[i][j]=(c[i][j]+(1LL*a[i][k]*b[k][j])%MOD)%MOD;
        }
    for (i=1; i<=n; ++i)
        for (j=1; j<=p; ++j)
            a[i][j]=c[i][j];
}

void solve ()
{
    rez[1][1]=rez[2][2]=1;
    sol[1][1]=0; sol[1][2]=1;
    a[1][1]=0; a[1][2]=a[2][1]=a[2][2]=1;
    for (--k; k; k>>=1)
    {
        if (k&1)
            mult (rez,a,2,2,2);
        mult (a,a,2,2,2);
    }
    mult (sol,rez,1,2,2);
    printf ("%d",sol[1][2]);
}

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

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

    return 0;
}