#include <algorithm>
using namespace std;

#define ll long long
#define MOD 666013
#define DIM 5

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

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

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

void solve ()
{
    int p;

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

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

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

    return 0;
}