#include <stdio.h>
#include <stdlib.h>

#define M 666013

void pow_matrix(long long a[])
{
    long long cpy[4];
    for (int i = 0; i < 4; i++)
        cpy[i] = a[i];

    a[0] = (cpy[0] * cpy[0] + cpy[1] * cpy[2]) % M;
    a[1] = (cpy[0] * cpy[1] + cpy[1] * cpy[3]) % M;
    a[2] = (cpy[2] * cpy[0] + cpy[3] * cpy[2]) % M;
    a[3] = (cpy[2] * cpy[1] + cpy[3] * cpy[3]) % M;
}

int exp_log(int f[], long long a[], int k)
{
    if (!k)
    {
        return f[0];
    }
    if (k & 1)
    {
        int cpy[2] = {f[0], f[1]};

        f[0] = (cpy[0] * a[0] + cpy[1] * a[2]) % M;
        f[1] = (cpy[0] * a[1] + cpy[1] * a[3]) % M;
        pow_matrix(a);
        return exp_log(f, a, (k - 1) / 2);
    }
    else
    {
        pow_matrix(a);
        return exp_log(f, a, k / 2);
    }
}

int main()
{
    FILE *fin = fopen("kfib.in", "rb");
    FILE *fout = fopen("kfib.out", "wb");

    int k, fib[] = {0, 1};
    long long a[] = {0, 1, 1, 1};

    fscanf(fin, "%d", &k);

    fprintf(fout, "%d\n", exp_log(fib, a, k));

    fclose(fin);
    fclose(fout);
    return 0;
}