#include <bits/stdc++.h>

using namespace std;
#define int long long int
#define pb push_back
#define sz(x) (int)(x.size())
#define all(a) a.begin(), a.end()
#define nl '\n'
const int N = 3e5 + 5, INF = 1e9, mod = 666013;

int k;

struct modint {
	int value;
	modint(long long value = 0) {
		if (abs(value) >= mod) {
			value %= mod;
		}
		if (value < 0) {
			value += mod;
		}
		this->value = value;
	}
	friend modint operator+(const modint& lhs, const modint& rhs) {
		return modint(lhs.value + rhs.value);
	}
	friend modint operator-(const modint& lhs, const modint& rhs) {
		return modint(lhs.value - rhs.value);
	}
	friend modint operator*(const modint& lhs, const modint& rhs) {
		return modint(1ll * lhs.value * rhs.value);
	}
	modint& operator+=(const modint& other) {
		return *this = modint(*this + other);
	}
	modint& operator-=(const modint& other) {
		return *this = modint(*this - other);
	}
	modint& operator*=(const modint& other) {
		return *this = modint(*this * other);
	}
	modint pow(long long e) const {
		modint res = 1, base = *this;
		for (; e > 0; e >>= 1) {
			if (e & 1) {
				res *= base;
			}
			base *= base;
		}
		return res;
	}
	modint inv() const {
		return this->pow(mod - 2);
	}
	friend modint operator/(const modint& lhs, const modint& rhs) {
		return lhs * rhs.inv();
	}
	modint& operator/=(const modint& other) {
		return *this = modint(*this / other);
	}
};

using matrix = vector<vector<int>>;

matrix build(int n, int m) {
	return vector<vector<int>>(n, vector<int>(m));
}

matrix multiply(matrix a, matrix b) {
	assert(a[0].size() == b.size());
	matrix c = build(a.size(), b[0].size());
	for (int i = 0; i < a.size(); ++i) {
		for (int j = 0; j < b[0].size(); ++j) {
			for (int k = 0; k < a[0].size(); ++k) {
				c[i][j] += a[i][k] * b[k][j] % mod;
				c[i][j] %= mod;
			}
		}
	}
	return c;
}

matrix pow(matrix a, int p) {
	assert(a.size() == a[0].size());
	matrix res = build(a.size(), a.size());
	for (int i = 0; i < a.size(); ++i) {
		res[i][i] = 1;
	}
	for (; p > 0; p >>= 1) {
		if (p & 1) {
			res = multiply(res, a);
		}
		a = multiply(a, a);
	}
	return res;
}

signed main() {
    cin >> k;
	matrix c = build(2, 2);
	matrix a = build(2, 1);
    c[0][1] = c[1][1] = c[1][0] = 1;
    a[0][0] = a[1][0] = 1;
	pow(c, k - 2);
	multiply(c, a);
	cout << c[2][1];
}