#include <stdio.h>
#include<vector>
#include<string.h>
#include<algorithm>
#include<map>
#include<iostream>
#include<sstream>


#define ll long long
#define P ((ll)666013)

using namespace std;

template <class T, int n, int m>
class mat
{
public:
    T A[n][m];

    static mat eye()
    {
	mat ans;

	for (int i = 0; i < n; i++)
	    ans[i][i] = 1;

	return ans;
    }

    mat()
    {
	memset(&A[0][0], 0, sizeof (A));
    }

    template<int p>
    mat<T, n, p> operator*(const mat<T, m, p> & b)
    {
	mat<T, n, p > res;

	for (int i = 0; i < n; i++)
	    for (int j = 0; j < p; j++)
		for (int k = 0; k < m; k++)
		    res.A[i][j] = (res.A[i][j] + A[i][k] * b.A[k][j]) % P;
	return res;
    }

    mat operator *(T x)
    {
	mat res;

	for (int i = 0; i < n; i++)
	    for (int j = 0; j < n; j++)
	    {
		res.A[i][j] = (A[i][j] * x) % P;
		while (res.A[i][j] < 0)
		    res.A[i][j] += P;
	    }
	return res;
    }

    mat operator +(const mat<T, n, m>& b)
    {
	mat res;

	for (int i = 0; i < n; i++)
	    for (int j = 0; j < m; j++)
		res.A[i][j] = (A[i][j] + b.A[i][j]) % P;

	return res;
    }

    mat operator -(const mat<T, n, m>& b)
    {
	mat res;

	for (int i = 0; i < n; i++)
	    for (int j = 0; j < m; j++)
	    {
		res.A[i][j] = (A[i][j] - b.A[i][j]) % P;
		while (res.A[i][j] < 0)
		    res.A[i][j] += P;
	    }

	return res;
    }

    void dbg(string s = "")
    {
	cerr << s << "\n";

	for (int i = 0; i < n; i++)
	{
	    for (int j = 0; j < m; j++)
		cerr << A[i][j] << " ";
	    cerr << "\n";

	}
	return;
    }

    void fill(T x)
    {
	for (int i = 0; i < n; i++)

	    for (int j = 0; j < m; j++)
		A[i][j] = x;
    }

    mat operator ^(long long x)
    {
	if (x == 0)
	    return eye();

	if (x == 1)
	{
	    return *this;
	}

	mat tmp = *this ^ (x / 2);
	mat ans = tmp *tmp;

	if (x % 2 == 1)
	    ans = ans * * this;

	return ans;
    }

    T * operator [] (int r)
    {
	return A[r];
    }

};

ll inv(ll a, ll PP)
{
    ll i = PP, v = 0, d = 1;

    while (a < 0)
	a = a + PP;

    while (a > 0)
    {
	ll t = i / a, x = a;
	a = i % x;
	i = x;
	x = d;
	d = v - t*x;
	v = x;
    }
    v %= PP;
    if (v < 0) v = (v + PP) % PP;
    return v;
}

#define n 40

int main()
{
    /*
	mat<ll, n, n > eye = mat<ll, n, n > ::eye();

	mat<ll, 5, 2 > u;
	mat<ll, 2, 5 > v;

	u.fill(1);
	v.fill(1);

	mat<ll, 5, 5 > t = u*v;

	(t + t * 3).dbg();

     */
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);

    ll k;
    cin >> k;

    mat<ll, 2, 1 > s;
    mat<ll, 2, 2 > t;


    s[0][0] = 1;
    s[0][1] = 0;

    t[0][0] = 1;
    t[0][1] = 1;
    t[1][0] = 1;
    t[1][1] = 0;

    t = t ^ k;

    cout << t[1][0];




}