#include <fstream>

using namespace std;

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

const long long mod = 666013;

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

void prod (long long m1[3][3], long long m2[3][3], long long rez[3][3], long long n, long long m, long long p)
{
    for (long long i = 1; i <= n; i++)
    {
        for (long long j = 1; j <= p; 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 <= n; i++)
    {
        for (long long j = 1; j <= p; j++)
        {
            rez[i][j] = aux[i][j];
        }
    }
}

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

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