#include<cstdio>
#include<cstring>
#define MOD 666013
using namespace std;
int Sol[5][5],M1[5][5],N;
inline void Mat_Prod(int A[][5],int B[][5],int Sol[][5])
{
    for (int i=1;i<=2;++i)
        for (int j=1;j<=2;++j)
            for (int k=1;k<=2;++k)
                Sol[i][j]+=(1LL*A[i][k]*B[k][j])%MOD, Sol[i][j]%=MOD;
}
inline void Load_Data(int &N)
{
    scanf("%d",&N);
    M1[1][1]=0,M1[1][2]=1,M1[2][1]=1,M1[2][2]=1;
}
inline void Put_Log(int P,int M[][5])
{
    int AUX[5][5],C[5][5];
    memcpy(C,M1,sizeof(M1)),M[1][1]=1,M[2][2]=1;
    for (int i=0; (1<<i) <=P;++i)
    {
        if (P & (1<<i))
            {
                memset(AUX,0,sizeof(AUX));
                Mat_Prod(M,C,AUX);
                memcpy(M,AUX,sizeof(AUX));
            }
        memset(AUX,0,sizeof(AUX));
        Mat_Prod(C,C,AUX);
        memcpy(C,AUX,sizeof(AUX));
    }
}
int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    Load_Data(N);
    Put_Log(N-1,Sol);
    printf("%d\n",Sol[2][2]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}