#include <cstdio>
#include <cstring>

using namespace std;

const int MOD = 666013;

int n;
int mat[3][3], mat2[3][3];

void init()
{
    mat[1][2] = mat[2][1] = mat[2][2] = mat2[1][2] = mat2[2][1] = mat2[2][2] = 1;
}

void inmulteste(int a[][3], int b[][3])
{
    int c[3][3];
    memset(c, 0, sizeof(c));
    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] + ((long long)a[i][k] * b[k][j])) % MOD;

    memcpy(a, c, sizeof(c));
}

void lgput(int x)
{
    if (x == 1)
        return;

    if (!(x & 1)) {
        lgput(x / 2);
        inmulteste(mat, mat);
    }
    else {
        lgput(x / 2);
        inmulteste(mat, mat);
        inmulteste(mat, mat2);
    }
}

int main()
{
    freopen ("kfib.in", "r", stdin);
    freopen ("kfib.out", "w", stdout);
    
    scanf("%d", &n);

    if (n == 0) {
        printf("0");
        return 0;
    }
    if (n <= 2) {
        printf("1");
        return 0;
    }
    init();
    lgput(n - 1);
    printf("%d", mat[2][2]);

    return 0;
}