#include <fstream>

using namespace std;

ifstream in ("kfib.in");
ofstream out ("kfib.out");

const long long mod = 666013;

long long ans[3][3], inm[3][3], aux[3][3], rez[3][3];

void prod (long long m1[3][3], long long m2[3][3], long long pr[3][3], long long n, long long m, long long p)
{
    for (long long i = 1; i <= m; i++)
    {
        for (long long j = 1; j <= m; j++)
        {
            aux[i][j] = 0;
        }
    }
    for (long long i = 1; i <= n; i++)
    {
        for (long long j = 1; j <= m; j++)
        {
            for (long long k = 1; k <= p; k++)
            {
                aux[i][j] = (aux[i][j] + (m1[i][k] * m2[k][j]) % mod) % mod;
            }
        }
    }
    for (long long i = 1; i <= m; i++)
    {
        for (long long j = 1; j <= m; j++)
        {
            pr[i][j] = aux[i][j];
        }
    }
}

void lgput (long long e, long long n, long long m[3][3])
{
    for (long long i = 1; i <= n; i++)
    {
        rez[i][i] = 1;
    }
    while (e > 0)
    {
        if (e % 2 == 1)
        {
            prod(rez, inm, rez, 2, 2, 2);
        }
        prod(m, m, m, 2, 2, 2);
        e /= 2;
    }
    for (long long i = 1; i <= n; i++)
    {
        for (long long j = 1; j <= n; j++)
        {
            m[i][j] = rez[i][j];
        }
    }
}

signed main ()
{
    long long n;
    in >> n;
    inm[1][2] = 1;
    inm[2][1] = 1;
    inm[2][2] = 1;
    lgput(n - 1, 2, inm);
    ans[1][1] = 1;
    ans[1][2] = 1;
    prod(ans, inm, ans, 1, 2, 2);
    out << ans[1][1];
    in.close();
    out.close();
    return 0;
}