#include <stdio.h>
#include <assert.h>
#include <algorithm>

using namespace std;

#define maxn 500010
#define mod 23456789 

int N, sol;
int A[maxn];

int main()
{
	freopen("algsort.in", "r", stdin);
	freopen("algsort.out", "w", stdout);

	int i;

	scanf("%d ", &N);

	assert(1<=N && N<=500000);

	for (i=1; i<=N; i++) 
	{
		scanf("%d ", &A[i]);
		assert(0<=A[i] && A[i]<=2147483647);
		assert(A[i]%mod || A[i]);
	}

	sort(A+1, A+N+1);

	for (i=1; i<=N; i++) sol = (sol + 1LL * A[i] * i) % mod;

	printf("%d\n", sol);

	return 0;
}