#include <bits/stdc++.h>

using namespace std;

const int MOD = 666013;

int Sol[2][2];
int k;

void mul(int A[2][2], int B[2][2], int C[2][2])
{
    int Fin[2][2];
    memset(Fin, 0, sizeof Fin);
    for (int i = 0; i <= 1; i++)
        for (int i1 = 0; i1 <= 1; i1++)
            for (int i2 = 0; i2 <= 1; i2++)
                Fin[i][i1] = ((Fin[i][i1] % MOD) + ((1ll * A[i][i2] * B[i2][i1]) % MOD)) % MOD;
    for (int i = 0; i < 2; i++)
        for (int i1 = 0; i1 < 2; i1++) C[i][i1] = Fin[i][i1];
}

void plog(int A1[2][2], int putere)
{
    A1[0][0] = A1[1][1] = 1, A1[0][1] = A1[1][0] = 0;
    int Constant[2][2];
    memset(Constant, 0, sizeof Constant);
    Constant[0][0] = 0, Constant[1][0] = Constant[0][1] = Constant[1][1] = 1;
    while (putere)
    {
        if (putere & 1)
        {
            putere--;
            mul(A1, Constant, A1);
        }
        putere >>= 1;
        mul(Constant, Constant, Constant);
    }
    printf("%d", A1[1][1]);
}

int main()
{
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    scanf("%d", &k);
    if (k <= 1) printf("%d", k);
    else plog(Sol, k - 1);
    return 0;
}