#include <cstdio>
#include <string.h>
#define NMod 666013

using namespace std;

long long rez[3][3],base[3][3],f[3][3],aux[3][3],n,pw;

void mat(long long a[][3],long long b[3][3],long long n,long long m,long long p) {
    memset(aux,0,sizeof(aux));
    for(long i=1;i<=n;i++)
        for(long j=1;j<=p;j++)
            for(long l=1;l<=m;l++)
                aux[i][j]=(aux[i][j]+a[i][l]*b[l][j])%NMod;

    for(long i=1;i<=n;i++)
        for(long j=1;j<=m;j++)
            a[i][j]=aux[i][j];
}

void lgpow(long long pw) {
    while(pw>1) {
        if(pw%2)
            mat(rez,base,2,2,2);
        mat(base,base,2,2,2);
        pw=pw>>1;
    }
    mat(rez,base,2,2,2);
}

int main()
{
    freopen("kfib.in","rt",stdin);
    freopen("kfib.out","wt",stdout);
    scanf("%ld",&n);
    pw=n-2;
    base[1][2]=base[2][1]=base[2][2]=1;
    rez[1][1]=rez[2][2]=1;
    lgpow(pw);
    f[1][1]=f[1][2]=1;
    mat(f,rez,1,2,2);
    printf("%ld",f[1][2]);
    return 0;
}