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 have 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 in the array ~A~, where ~A[i]~ represents both the laziness level of the ~i^{th}~ student and the difficulty of their 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 have asked you what is the shortest possible (total) time they must spend to finish all tasks.

Input Specification

The first line of input contains the integer ~N~, which represents the total number of tasks. The next ~N~ lines contain exactly one integer each, which represents the difficulty of the task and the laziness of the student who initially received the task.

Output Specification

Your output should consist of only one line – the minimum time needed to finish all tasks, modulo ~10\,007~.

Constraints

• ~1 \le N \le 100\,000~
• ~1 \le A[i] \le 100\,000~

Sample Input

2
1
3

Sample Output

6

Explanation

If the students switch their tasks, they will be able to finish them in ~3+3=6~ time units.