#include <stdio.h>
#include <stdlib.h>

#define MOD 23456789

int N, x, V[ 500010 ];
long long S, i;

int sortf( const void *x, const void *y ) {
	return *(int *)x - *(int *)y;
}

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

	scanf( "%d", &N );
	
	for( i = 1; i <= N; i++ )
		scanf( "%d", &V[i] );

	qsort( V+1, N, sizeof( V[1] ), sortf );

	for( S = 0, i = 1; i <= N; i++ )
		S = ( S + i*V[i] ) % MOD;

	printf( "%lld\n", S );

	return 0;
}