#include <iostream>
using namespace std;

const int MOD = 45678;

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int N;
	cin >> N;
	
	int result = 5;
	
	for (int i = 1; i < N; i++)
	{
		result = (result + (i + 2) * 3 - 2) % MOD;
	}

	cout << result << "\n";

	return 0;
}