/*
	DRZAVNO TAKMICENJE 2008
	ZADATAK: trojke
	AUTOR: Aleksandar i Andreja Ilic, Nis

	Za svaku uredjenu strago rastucu trojku indeksa (i, j, k)
  treba sabrati max (a_i, a_j, a_k). Na pocetku sortiramo niz
  u nerastucem poredtku. Broj a [1] je najveci u svakoj trojci u
  kojoj se nalazi - dakle tacno (n - 1)(n - 2) / 2 puta. Slicno
  dobijamo da se a [k] pojavljuje (n - k)(n - k - 1) / 2 puta.
  	
    Pri mnozenju moramo paziti da ne dodje do prekoracenja,
  tako da posle svakog sabiranja i mnozenja uzimamo ostatak pri
  deljenju sa 10007.

  	Vremenska slozenost gore navedenog algoritma je O(n log n),
  dok je memorijska O (n).
*/

#include <stdlib.h>
#include<stdio.h>
#include <time.h> 
#define maxN 30005
#define mod 10007

int n, sol, a [maxN];
FILE *in, *out;

	// Permutovanje niza
	void mixArray()
	{
        srand(time(0));
		for (int k = 1; k < n; k++)
		{
			int x = rand() % k;
			int tmp = a [x]; 
            a [x] = a [k]; 
            a [k] = tmp;
		}
	}

	// Sortiranje niza
	void Sort (int l,  int d)
	{
		int tmp, pivot, i, j;
		if (l < d)
		{
			pivot = a [(l + d) / 2];
			i = l; 
			j = d;
			do
			{
				while (a [i] > pivot) i++;
				while (a [j] < pivot) j--;
				if (i <= j)
				{
     				tmp = a [i]; a [i] = a [j]; a [j] = tmp;
					i++; j--;
				}
			}
			while (i <= j);
			Sort (l, j);
			Sort (i, d);
			}
	}

	// Glavna fja
	void Solve()
	{
        mixArray();
		Sort(0, n - 1);
		for (int i = 0; i < n; i++)
		{
		    a [i] = a [i] % mod;
		    if (a [i] < 0)
		       a [i] += mod;
        }
		sol = 0;
		for (int i = 0; i < n - 2; i++)
		{
            int tmp = (n - i - 1) * (n - i - 2) / 2;
            if (tmp > mod)
               tmp = tmp % mod;
            sol += tmp * a [i];
            if (sol > mod)
               sol = sol % mod;
		}
	}

    // Unos podataka
	void InPut()
	{
		in = fopen ("trojke.in", "r");
		fscanf (in, "%d", &n);
		for (int i = 0; i < n; i++)
			fscanf (in, "%d", &a [i]);
		fclose(in);
	}

	// Ispis resenja
	void OutPut()
	{
		out = fopen ("trojke.out", "w");
		fprintf (out, "%d\n", (int) sol);
		fclose(out);
	}

int main()
{
	InPut();
	Solve();
	OutPut();
	return 0;
}