#include <bits/stdc++.h>
#include <bitset>

#define mod 666013

using namespace std;

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

void matrix_multiplication(long long m1[3][3], long long m2[3][3], uint8_t i)
{
    int a = (m1[0][0] * m2[0][0]) % mod + (m1[0][1] * m2[1][0]) % mod;
    int b = (m1[0][0] * m2[0][1]) % mod + (m1[0][1] * m2[1][1]) % mod;
    int c = (m1[1][0] * m2[0][0]) % mod + (m1[1][1] * m2[1][0]) % mod;
    int d = (m1[1][0] * m2[0][1]) % mod + (m1[1][1] * m2[1][1]) % mod;

    m1[0][0] = a % mod;
    m1[0][1] = b % mod;
    m1[1][0] = c % mod;
    m1[1][1] = d % mod;

    // if (a < 0 || b < 0 || c < 0 || d < 0)
    // {
    //     cout << "ai belit o " << (int)i << endl;
    //     cout << m1[0][0] << " " << m1[0][1] << "\n"
    //          << m1[1][0] << " " << m1[1][1] << "\n\n\n";
    // }
    // cout << "call miplipllication"
    //      << "\n";
}

void raise_matrix_to_power(long long m[3][3], uint32_t k)
{
    long long sol[3][3];
    sol[0][0] = 1;
    sol[0][1] = 0;
    sol[1][0] = 0;
    sol[1][1] = 1;

    // std::bitset<32> binary(k);
    // std::cout << "Binary representation of " << k << ": " << binary << std::endl;

    for (uint8_t i = 0; (1 << i) <= k; ++i)
    {
        if ((1 << i) & k)
            matrix_multiplication(sol, m, i);

        matrix_multiplication(m, m, i);
    }

    m[0][0] = sol[0][0];
    m[0][1] = sol[0][1];
    m[1][0] = sol[1][0];
    m[1][1] = sol[1][1];
}

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

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

    long long fibbo_matrix[3][3];
    fibbo_matrix[0][0] = 0;
    fibbo_matrix[0][1] = 1;
    fibbo_matrix[1][0] = 1;
    fibbo_matrix[1][1] = 1;
    raise_matrix_to_power(fibbo_matrix, k - 1);

    // cout << "raspuns:\n"
    //      << fibbo_matrix[0][0] << " " << fibbo_matrix[0][1] << "\n"
    //      << fibbo_matrix[1][0] << " " << fibbo_matrix[1][1] << "\n";

    out << fibbo_matrix[1][1] << "\n";

    return 0;
}