#include<cstdio>
#include<cstring>

#define MOD 666013
using namespace std;

int Sol[3][3],Z[3][3];
int k;

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

inline void LogPower(int n,int M[][3])
{
    int C[3][3],AUX[3][3],i;
    memcpy(C,Z,sizeof(Z));
    M[0][0]=1;
    M[1][1]=1;

    for (i=0;(1 << i)<=n;i++)
    {
        if (n & (1 << i))
            {
                memset(AUX,0,sizeof(AUX));
                MatProd(M,C,AUX);
                memcpy(M,AUX,sizeof(AUX));
            }
          memset(AUX,0,sizeof(AUX));
          MatProd(C,C,AUX);
          memcpy(C,AUX,sizeof(AUX));
    }
}

inline void ConstDef()
{
    Z[0][0]=0;
    Z[1][0]=1;
    Z[0][1]=1;
    Z[1][1]=1;
}

int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d",&k);
    ConstDef();
    memset(Sol,0,sizeof(Sol));
    LogPower(k-1,Sol);
    printf("%d\n",Sol[1][1]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}