#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
const int MOD = 666013;
struct mat
{

    int size;
    vector<vector<long long>> val;
    mat operator*(mat other)
    {
        mat temp(size);
        for (int i = 0; i < size; i++)
        {
            for (int j = 0; j < size; j++)
            {
                long long s = 0;
                for (int k = 0; k < size; k++)
                {
                    s += val[i][k] * other.val[k][j];
                }
                temp.val[i][j] = s;
            }
        }

        return temp;
    }
    mat &operator*=(mat &other)
    {
        mat temp(size);
        for (int i = 0; i < size; i++)
        {
            for (int j = 0; j < size; j++)
            {
                long long s = 0;
                for (int k = 0; k < size; k++)
                {
                    s += val[i][k] * other.val[k][j];
                }
                temp.val[i][j] = s;
            }
        }
        val = temp.val;
        return *this;
    }
    mat &operator%=(const int &mod)
    {
        for (auto &i : val)
            for (auto &j : i)
                j %= MOD;
        return *this;
    }
    mat(int size)
    {
        this->size = size;
        val = vector<vector<long long>>(size, vector<long long>(size, 0));
        for (int i = 0; i < size; val[i][i] = 1, i++)
            ;
    }
    mat(vector<vector<long long>> &vec)
    {
        val = vec;
        size = vec.size();
    }
    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(2);

    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;
    vector<vector<long long>> temp = {{0, 1}, {1, 1}};
    mat m(temp);
    fout << exp(m, n).val[0][1];
    return 0;
}