#include <cstdio>
#include <cstring>
#define MOD 666013
using namespace std;

int k,M[3][3],aux[3][3],R[3][3],F[3][3];

inline void init()
{
    R[1][1]=1;R[1][2]=0;
    R[2][1]=0;R[2][2]=1;

    F[1][1]=1;F[1][2]=1;

    M[1][1]=0;M[1][2]=1;
    M[2][1]=1;M[2][2]=1;
    return;
}

inline void inm(int A[3][3],int B[3][3],int C[3][3],int l1,int l2)
{
    C[1][1]=C[1][2]=C[2][1]=C[2][2]=0;
    for(int i=1;i<=l1;++i)
        for(int j=1;j<=l2;++j)
          for(int k=1;k<=2;++k)
            C[i][j]=(1LL*C[i][j]+1LL*A[i][k]*B[k][j])%MOD;
    return;
}

inline void putere(int nr)
{
    for(int i=0;(1<<i)<=nr;++i)
    {
        if((nr>>i)&1)
        {
            inm(M,R,aux,2,2);
            memcpy(R,aux,sizeof(aux));
        }
        inm(M,M,aux,2,2);
        memcpy(M,aux,sizeof(aux));
    }
    return;
}

int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d",&k);
    if(!k)
    {
        printf("0\n");
        return 0;
    }
    init();
    --k;
    putere(k);
    inm(F,R,aux,1,2);
    printf("%d\n",aux[1][1]);
    return 0;
}