#include <fstream>
#define R 666013

using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");

void mult(long long a[2][2], long long b[2][2]);
long long putere(long long b[2][2], long long p);
long long fib(long long n);

int main()
{
    long long n;
    fin >> n;
    fout << fib(n) << '\n';
    return 0;
}

void mult(long long a[2][2], long long b[2][2])
{
    long long rez[2][2];
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            rez[i][j] = 0;

    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                rez[i][j] = (rez[i][j] + a[i][k] * b[k][j]) % R;

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

long long putere(long long b[2][2], long long p)
{
    long long aux[2][2];
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            aux[i][j] = b[i][j];

    while (p)
    {
        if (p % 2)
            mult(aux, b);
        mult(b, b);
        p /= 2;
    }

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

long long fib(long long n)
{
    long long a[1][2] = { { 0, 1 } };
    long long b[2][2] = { { 0, 1 } , { 1, 1 } };
    putere(b, n - 1);
    mult(a, b);

    long long rez = a[0][0];
    return rez;
}