#include <fstream>
#include <map>
#define MOD 666013

using namespace std;

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

long long x[4][4];
long long z[4][4];
long long e[4][4];
map <long long, long long[4][4]> y;

void inmult(long long x[][4], long long y[][4])
{
    e[1][1] = 0;
    e[1][2] = 0;
    e[2][2] = 0;
    e[2][1] = 0;

    for(long long i = 1; i <= 2; ++i)
    {
        for(long long j = 1; j <= 2; ++j)
        {
            for(long long w = 1; w <= 2; ++w)
            {
                e[i][j] += x[i][w] * y[w][j];
                e[i][j] %= MOD;
            }
        }
    }

    for(long long i = 1; i <= 2; ++i)
    {
        for(long long j = 1; j <= 2; ++j)
        {
            x[i][j] = e[i][j];
        }
    }
}

void power(long long n)
{
    if(n == 1)
        return;

    if(y.find(n) != y.end())
        return;

    y[n][1][1] = 1;
    y[n][2][2] = 1;
    power(n / 2);
    inmult(y[n], y[n / 2]);
    inmult(y[n], y[n / 2]);

    if(n % 2 == 1)
        inmult(y[n], y[1]);
}

int main()
{
    x[1][1] = 1;
    x[2][2] = 1;

    y[1][1][2] = 1;
    y[1][2][2] = 1;
    y[1][2][1] = 1;

    z[1][1] = 1;
    z[1][2] = 1;

    long long k;
    cin >> k;

    if(k == 1 || k == 2)
    {
        cout << 1 << '\n';
        return 0;
    }

    ++k;
    power(k);
    inmult(x, y[k]);
    inmult(x, z);
    cout << x[1][2] % MOD << '\n';
    return 0;
}