#include <bits/stdc++.h>
#define objl '\n'
typedef long long ll;
using namespace std;
//数据结构在这里定义 
ll n;
ll m = 123456789;


ll bpm(ll b, ll p, ll m){
	ll res = 1 % m;
	while(p!=0){
		if(p&1){
			res = (res % m) * (b % m) % m;
		}
		b = (b % m) * (b % m) % m;
		p = p >> 1;
	}
	return res;
}



void solve(){
//cin cout在这里 
	cin >> n;
	ll ans = 0;
	for(int x = 1; x<= n; x++){
		ans = ((ans % m) + (bpm(x,8,m) % m)) % m;
	}
	cout << ans << endl;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;//多组数据要cin
	//cin >> t;
	t = 1;
	while(t--){
		solve();
	} 
	return 0;//必须加return 0 
}