#include <fstream>
#include <iostream>

using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
const int MOD = 666013;
struct mat
{
    long long val[2][2];

    mat operator*(mat other)
    {
        mat temp;

        temp.val[0][0] = this->val[0][0] * other.val[0][0] + this->val[0][1] * other.val[1][0];
        temp.val[0][1] = this->val[0][0] * other.val[0][1] + this->val[0][1] * other.val[1][1];
        temp.val[1][0] = this->val[1][0] * other.val[0][0] + this->val[1][1] * other.val[1][0];
        temp.val[1][1] = this->val[1][0] * other.val[0][1] + this->val[1][1] * other.val[1][1];

        return temp;
    }
    mat operator*=(mat &other)
    {
        mat temp;

        temp.val[0][0] = this->val[0][0] * other.val[0][0] + this->val[0][1] * other.val[1][0];
        temp.val[0][1] = this->val[0][0] * other.val[0][1] + this->val[0][1] * other.val[1][1];
        temp.val[1][0] = this->val[1][0] * other.val[0][0] + this->val[1][1] * other.val[1][0];
        temp.val[1][1] = this->val[1][0] * other.val[0][1] + this->val[1][1] * other.val[1][1];

        val[0][0] = temp.val[0][0];
        val[1][0] = temp.val[1][0];
        val[1][1] = temp.val[1][1];
        val[0][1] = temp.val[0][1];
        return *this;
    }
    mat operator%=(const int &mod)
    {
        val[0][0] %= mod;
        val[1][0] %= mod;
        val[1][1] %= mod;
        val[0][1] %= mod;

        return *this;
    }
    mat()
    {
        val[0][0] = 1;
        val[0][1] = 0;
        val[1][0] = 0;
        val[1][1] = 1;
    }
    mat(const int a, const int b, const int c, const int d)
    {
        val[0][0] = a;
        val[0][1] = b;
        val[1][0] = c;
        val[1][1] = d;
    }
    friend ostream &operator<<(ostream &os, const mat &m)
    {
        os << m.val[0][0] << " " << m.val[0][1] << '\n'
           << m.val[1][0] << " " << m.val[1][1] << '\n';
    }
};
mat exp(mat b, long long e)
{
    mat r;

    while (e)
    {
        if (e & 1 == 1)
        {
            r *= b;
            r %= MOD;
        }
        b = b * b;
        b %= MOD;
        e >>= 1;
    }
    return r;
}
int main()
{
    int n;
    fin >> n;
    mat m(0, 1, 1, 1);
    fout << exp(m, n).val[0][1];
    return 0;
}