#include <iostream>

using namespace std;

using ll = long long; 

ll mod = 123456789;

ll myPow(ll a, ll b) {
	ll res = 1;
	while (b) {
		if (b & 1)
			res = res * a % mod;
		b >>= 1;
		a = a * a % mod;
	}
	return res;
}

int main() {
	int n;
	cin >> n;
	ll res = 0;
	for (int i = 1; i <= n; ++i) {
		res = (res + myPow(i, 8)) % mod;
	}
	
	cout << res << '\n';
	
	return 0;
}