#include <stdio.h>

#define MOD 123457

int N, V[ 500010 ];

//Swap two integers
void swap(int* a, int* b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

//Find the index of the Median of the elements
//of array that occur at every "shift" positions.
int findMedianIndex(int* array, int left, int right, int shift)
{
    int i, groups = (right - left)/shift + 1, k = left + groups/2*shift;
    for(i = left; i <= k; i+= shift)
    {
        int minIndex = i, minValue = array[minIndex], j;
        for(j = i; j <= right; j+=shift)
            if(array[j] < minValue)
            {
                minIndex = j;
                minValue = array[minIndex];
            }
        swap(&array[i], &array[minIndex]);
    }
 
    return k;
}

//Computes the median of each group of 5 elements and stores
//it as the first element of the group. Recursively does this
//till there is only one group and hence only one Median
int findMedianOfMedians(int* array, int left, int right)
{
    if(left == right)
        return array[left];
 
    int i, shift = 1;
    while(shift <= (right - left))
    {
        for(i = left; i <= right; i+=shift*5)
        {
            int endIndex = (i + shift*5 - 1 < right) ? i + shift*5 - 1 : right;
            int medianIndex = findMedianIndex(array, i, endIndex, shift);
 
            swap(&array[i], &array[medianIndex]);
        }
        shift *= 5;
    }
 
    return array[left];
}

//Partition the array into two halves and return the
//index about which the array is partitioned
int partition(int* array, int left, int right)
{
    //Makes the leftmost element a good pivot,
    //specifically the median of medians
    findMedianOfMedians(array, left, right);
    int pivotIndex = left, pivotValue = array[pivotIndex], index = left, i;
 
    swap(&array[pivotIndex], &array[right]);
    for(i = left; i < right; i++)
    {
        if(array[i] < pivotValue)
        {
            swap(&array[i], &array[index]);
            index += 1;
        }
    }
    swap(&array[right], &array[index]);
 
    return index;
}
 
//Quicksort the array
void quicksort(int* array, int left, int right)
{
    if(left >= right)
        return;
 
    int index = partition(array, left, right);
    quicksort(array, left, index - 1);
    quicksort(array, index + 1, right);
}

int main() {
	long long S, i;

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

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

	quicksort( V, 1, N );

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

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

	return 0;
}