CF717C.Potions Homework

Harry Water, Ronaldo, Her-my-oh-knee and their friends have started a new school year at their MDCS School of Speechcraft and Misery. At the time, they are very happy to have seen each other after a long time. The sun is shining, birds are singing, flowers are blooming, and their Potions class teacher, professor Snipe is sulky as usual. Due to his angst fueled by disappointment in his own life, he has given them a lot of homework in Potions class.

Each of the n students has been assigned a single task. Some students do certain tasks faster than others. Thus, they want to redistribute the tasks so that each student still does exactly one task, and that all tasks are finished. Each student has their own laziness level, and each task has its own difficulty level. Professor Snipe is trying hard to improve their work ethics, so each student’s laziness level is equal to their task’s difficulty level. Both sets of values are given by the sequence a, where a__i represents both the laziness level of the i-th student and the difficulty of his task.

The time a student needs to finish a task is equal to the product of their laziness level and the task’s difficulty. They are wondering, what is the minimum possible total time they must spend to finish all tasks if they distribute them in the optimal way. Each person should receive one task and each task should be given to one person. Print the answer modulo 10 007.

哈利·沃特、罗纳尔多、赫敏—哦—尼以及他们的朋友们在MDCS魔药与苦难言说学院开启了新学年。此时，他们久别重逢，心情格外愉悦。阳光明媚，鸟语花香，而他们的魔药课教授斯耐普却一如往常地阴沉着脸。由于自身生活的失意所催生的愤懑情绪，他给学生们布置了大量魔药课作业。

共有 $ n $ 名学生，每人被分配了一项任务。不同学生完成同一任务所需时间各不相同。因此，他们希望重新分配这些任务，使得每名学生仍恰好完成一项任务，且所有任务均被完成。每名学生都有其对应的懒惰值，每项任务也都有其对应的难度值。斯耐普教授正竭力提升学生们的劳动伦理，因此每名学生的懒惰值恰好等于其所分配任务的难度值。这两组数值均由序列 $ a $ 给出：其中 $ a_i $ 既表示第 $ i $ 名学生的懒惰值，也表示其原分配任务的难度值。

一名学生完成某项任务所需时间为该学生的懒惰值与该任务难度值的乘积。他们想知道：若以最优方式重新分配任务（即每人分配一项任务，每项任务分配给一人），完成全部任务所需的最短总时间是多少？请输出答案对 $ 10,007 $ 取模的结果。

The first line of input contains integer n (1 ≤ n ≤ 100 000) — the number of tasks. The next n lines contain exactly one integer number a__i (1 ≤ a__i ≤ 100 000) — both the difficulty of the initial task and the laziness of the i-th students.

输入的第一行包含一个整数 $n$（$1 ≤ n ≤ 100\,000$）——任务的数量。接下来的 $n$ 行每行恰好包含一个整数 $a_i$（$1 ≤ a_i ≤ 100\,000$）——既表示初始任务的难度，也表示第 $i$ 个学生的懒惰值。

Print the minimum total time to finish all tasks modulo 10 007.

输出完成所有任务的最小总时间对 10 007 取模的结果。

In the first sample, if the students switch their tasks, they will be able to finish them in 3 + 3 = 6 time units.

在第一个样例中，如果学生们交换他们的任务，他们将能在 $3 + 3 = 6$ 个时间单位内完成这些任务。