#include <fstream>

using namespace std;

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

#define MOD 666013

int x[2][2];

void inmultire(int rez[2][2], int a[2][2], int b[2][2])
{
    long long aux[2][2];

    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
        {
            aux[i][j] = 0;
            for(int k = 0; k < 2; k++)
                aux[i][j] += (long long)a[i][k] * b[k][j];

            aux[i][j] %= MOD;
        }

    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
            rez[i][j] = aux[i][j];
}

void putere(int p)
{
    if(p == 1)
        return;

    if(p == 0)
    {
        for(int i = 0; i < 2; i++)
            for(int j = 0; j < 2; j++)
                x[i][j] = (i ^ j) ^ 1;

        return;
    }

    if(p % 2)
    {
        int aux[2][2];

        for(int i = 0; i < 2; i++)
            for(int j = 0; j < 2; j++)
                aux[i][j] = x[i][j];

        inmultire(x, x, x);
        putere(p / 2);
        inmultire(x, aux, x);
        return;
    }

    inmultire(x, x, x);
    putere(p / 2);
}

int main()
{
    int k;
    in >> k;

    if(k == 0)
    {
        out << 0 << '\n';
        return 0;
    }

    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
            x[i][j] = i | j;

    putere(k - 1);
    out << x[1][1] << '\n';
}