#include <stdio.h>
#define mod 666013
FILE *fin = NULL, *fout = NULL;

void inmultire(long long int a[2][2], long long int b[2][2])
{
    long long int c[2][2];
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
        {
            c[i][j] = 0;
            for (int k = 0; k < 2; ++k)
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]);
            c[i][j] = c[i][j] % mod;
        }
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
            a[i][j] = c[i][j];
}

void putere(long long a[2][2], long long b[2][2], long long n)
{
    while (n > 0)
    {
        if (n % 2 == 1)
            inmultire(b, a);
        inmultire(a, a);
        n = n / 2;
    }
}

int main()
{

    long long a[2][2], b[2][2], n;

    fin = fopen("kfib.in", "r");
    fout = fopen("kfib.out", "w");
    fscanf(fin, "%lld", &n);

    // Initializam cu matricea Z
    a[0][0] = 0;
    a[0][1] = 1;
    a[1][0] = 1;
    a[1][1] = 1;

    // Initializam cu matricea identitate
    b[0][0] = 1;
    b[0][1] = 0;
    b[1][0] = 0;
    b[1][1] = 1;

    putere(a, b, n);
    fprintf(fout, "%lld", b[0][1]);

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