#include<stdio.h>
#include<string.h>
#define mod 666013

long long N, i;
long long MAT[3][3], REZ[3][3];

void inmultire(long long A[][3], long long B[][3], long long C[][3])
{
    long long 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] +  A[i][k] * B[k][j]) % mod;
}

void pow(long long M[][3], long long P)
{
    long long C[3][3], AUX[3][3], i;

    memcpy(C, MAT, sizeof(MAT));
    M[0][0] = M[1][1] = 1;

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

        memset(AUX, 0, sizeof(AUX));
        inmultire(C, C, AUX);
        memcpy(C, AUX, sizeof(C));
    }
}

int main()
{
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);

    scanf("%lld", &N);
    MAT[0][0] = 0;
    MAT[0][1] = 1;
    MAT[1][0] = 1;
    MAT[1][1] = 1;

    pow(REZ, N-1);
    printf("%lld\n", REZ[1][1]);

    return 0;
}