#include <bits/stdc++.h>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
const int MOD = 666013;

void Multiply(int A[2][2], int B[2][2])
{
    int p[2][2], i, j;
    p[0][0] = (1LL * A[0][0] * B[0][0] + 1LL * A[0][1] * B[1][0]) % MOD;
    p[0][1] = (1LL * A[0][0] * B[0][1] + 1LL * A[0][1] * B[1][1]) % MOD;
    p[1][0] = (1LL * A[1][0] * B[0][0] + 1LL * A[1][1] * B[1][0]) % MOD;
    p[1][1] = (1LL * A[1][0] * B[0][1] + 1LL * A[1][1] * B[1][1]) % MOD;

    for(i = 0; i < 2; i++)
        for(j = 0; j < 2; j++)
            A[i][j] = p[i][j];
}

void Expolog(int A[2][2], int n)
{
    int p[2][2] = {{1, 0}, {0, 1}}, x[2][2] = {{A[0][0], A[0][1]}, {A[1][0], A[1][1]}}, i, j;
    while (n > 0)
    {
        if (n % 2 == 1) Multiply(p, x);
        n /= 2;
        Multiply(x, x);
    }
    for(i = 0; i < 2; i++)
        for(j = 0; j < 2; j++)
            A[i][j] = p[i][j];
}

int Fib(int k)
{
    if (k == 0) return 0;
    if (k == 1) return 1;
    int F[2][2] = {{1, 1}, {1, 0}};
    Expolog(F, k - 1);
    return F[0][0];
}

int main()
{
    int k;
    fin >> k;
    fout << Fib(k) << "\n";
    return 0;
}