#include <bits/stdc++.h>
using namespace std;

#define ll unsigned long long 
#define mat vector < vector < ll>>
#define fisier 1
const int mxA = 2e6, M = 666013;
const ll M2 = (ll)M*M;
mat cn(int n, int m){
	return vector < vector < ll>> (n, vector<ll>(m));
}
mat mult(mat &a, mat &b){
	mat c = cn(a.size(), b[0].size());
	for (unsigned i = 0; i < a.size(); ++i){
		for (unsigned k = 0; k < b.size(); ++k){
			for (unsigned j = 0; j < b[0].size(); ++j){
				c[i][j] += a[i][k] * b[k][j];
				if (c[i][j] >= M2)
					c[i][j] -=M2;
			}
		}
	}
	for (unsigned i = 0; i < a.size(); ++i)
		for (unsigned j = 0; j < b[0].size(); ++j)
			c[i][j] %=M;
	return c;
}

int32_t main(){
	#ifdef fisier
        ifstream cin("kfib.in");
        ofstream cout("kfib.out");
    #endif

	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	ll n;
	cin >> n;
	mat r = {{0,1}};
	mat b= {{0,1}, {1,1}};
	while (n){
		if (n&1) r = mult(r,b);
		b = mult(b, b);
		n/=2;
	}
	cout << r[0][0];
}