#include <bits/stdc++.h>
using namespace std;
#define int long long
// #define LL long long
#define endl '\n'

const int MOD = 123456789;

int n;

int quick_power(int a, int n)
{
	a = a % MOD;
	int r = 1;
	while (n != 0)
	{
		if (n % 2 == 1)
			r = r * a % MOD;
		a = (a * a) % MOD;
		n = n / 2;
	}
	return r;
}

void solve()
{
	cin >> n;
	int sum = 0;
	for (int i = 1; i <= n; i++)
	{
		sum += quick_power(i, 8);
	}
	cout << sum % MOD;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	solve();

	return 0;
}