#include <cstdio>
#include <cstring>
#define MOD 666013
#define Nmx 3

using namespace std;

int m[Nmx][Nmx],sol[Nmx][Nmx],a[Nmx][Nmx],n;

void mult(int x[Nmx][Nmx],int y[Nmx][Nmx],int n,int m,int m1)
{
    int c[Nmx][Nmx];
    memset(c,0,sizeof(c));
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
        {
            c[i][j]=0;
            for(int k=1;k<=m1;++k)
                c[i][j]=(c[i][j]+(1LL*x[i][k]*y[k][j])%MOD)%MOD;
        }
     memcpy(x,c,sizeof(c));
}

int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d",&n);
    if(n==0) {printf("0\n");return 0;}
    if(n==1) {printf("1\n");return 0;}
    sol[1][1]=sol[2][2]=1;
    a[1][1]=a[1][2]=a[2][1]=1;
    while(n)
    {
        if(n&1)
            mult(sol,a,2,2,2);
        mult(a,a,2,2,2);
        n>>=1;
    }
    m[1][1]=0;m[1][2]=1;
    mult(m,sol,1,2,2);
    printf("%d\n",m[1][1]);
    return 0;
}