#include <cstdio>
#define MOD 666013

using namespace std;

int a[5][5],b[5][5];

inline void Mult_Mat(int a[][5], int b[][5])
{
    int c[5][5],i,j,k;
    for(i=1;i<=2;++i)
        for(k=1;k<=2;++k) c[i][k]=0;
    for(i=1;i<=2;++i)
        for(k=1;k<=2;++k)
            for(j=1;j<=2;++j)
                c[i][j]=(c[i][j]+1LL*a[i][k]*b[k][j])%MOD;

    for(i=1;i<=2;++i)
        for(j=1;j<=2;++j)
            a[i][j]=c[i][j];
}

inline void Pow_Log(int a[][5], int p)
{
    int put[5][5],i,j;
    for(i=0;i<=4;++i)
        for(j=0;j<=4;++j)
            put[i][j]=0;
    put[1][1]=put[2][2]=1;
    while(p)
    {
        if(p&1)
        {
            --p;
            Mult_Mat(put,a);
        }
        p>>=1;
        Mult_Mat(a,a);
    }
    for(i=1;i<=2;++i)
        for(j=1;j<=2;++j)
            a[i][j]=put[i][j];
}

int main()
{
    int N;
    freopen ("kfib.in","r",stdin);
    freopen ("kfib.out","w",stdout);
    scanf("%d", &N);
    if(!N)
        printf("0\n");
    else
    {
        a[1][2]=1;
        b[1][2]=b[2][1]=b[2][2]=1;
        Pow_Log(b,N-1);
        Mult_Mat(a,b);
        printf("%d\n", a[1][2]);
    }
    return 0;
}