#include <bits/stdc++.h>
# define modulo 666013

using namespace std;

int n;
int f[7][7], m[7][7];
/**
    TEORIE:

    fi = (fi-1, fi)

    m = (0, 1)
        (1, 1)

    (fi - 2, fi - 1) *  (0, 1) = (fi - 1, fi)
                        (1, 1)

    fi = fi-1 * m
    fi = fi-2 * m^2,    fi = fi-1 * m

    .
    .
    .

!!! fi = f1 * m^(i-1) !!!

//*/

void Inmultire(int a[7][7], int b[7][7])
{
    int c[7][7], i, j, k;
    long long s;
    for (i = 1; i <= 2; i++)
        for (j = 1; j <= 2; j++)
        {
            s = 0;
            for (k = 1; k <= 3; k++)
                s += (1LL * a[i][k] * b[k][j]);
            c[i][j] = s % modulo;
        }

    for (i = 1; i <= 2; i++)
        for (j = 1; j <= 2; j++)
            a[i][j] = c[i][j];
}

void MatricePutere(int n)
{
    int aux[7][7];
    /// matricea unitate
    aux[1][1] = aux[2][2] = 1;
    aux[1][2] = aux[2][1] = 0;

    while (n)
    {
        if (n % 2 == 1)
            Inmultire(aux, m);
        Inmultire(m, m);
        n /= 2;
    }

    for (int i = 1; i <= 2; i++)
        for (int j = 1; j <= 2; j++)
            m[i][j] = aux[i][j];
}

int main()
{
    ifstream fin ("kfib.in");
    ofstream fout ("kfib.out");
    fin >> n;
    /// matricea f
    f[1][2] = 1;
    /// matricea m
    m[1][2] = m[2][1] = m[2][2] = 1;

    MatricePutere(n - 1);
    Inmultire(f, m);
    fout << f[1][2] << "\n";
    fin.close();
    fout.close();
    return 0;
}