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