#include<cstdio>
#include<cstring>
using namespace std;
const int MOD = 666013;
int i,K,Exp,Z[3][3],SOL[3][3],AUX[3][3];
void Mult(int C[][3],int A[][3],int B[][3])
{
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            for(int k=1;k<=2;k++)
                C[i][j]=(C[i][j]+1LL*A[i][k]*B[k][j])%MOD;
}
int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d",&K); Exp=K-1;
    Z[1][2]=Z[2][1]=Z[2][2]=1;
    SOL[1][1]=SOL[2][2]=1;
    for(i=1;i<=Exp;i<<=1)
    {
        if(i&Exp)
        {
            memset(AUX,0,sizeof(AUX));
            Mult(AUX,SOL,Z);
            memcpy(SOL,AUX,sizeof(AUX));
        }
        memset(AUX,0,sizeof(AUX));
        Mult(AUX,Z,Z);
        memcpy(Z,AUX,sizeof(AUX));
    }
    printf("%d\n",SOL[2][2]);
    return 0;
}