#include <fstream>
#include <algorithm>

using namespace std;

#define MOD 123457

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

int main() {
	ifstream fi( "algsort.in" );
	ofstream fo( "algsort.out" );

	fi >> N;
	for( i = 1; i <= N; i++ )
		fi >> V[i];

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

	fo << S << '\n';

	fo.close(); fi.close();

	return 0;
}