哈里·沃特、罗纳尔多、Her-my-oh-knee 和他们的朋友们已经在 MDCS 言语技巧和痛苦学校开始了新学年。当时,久别重逢,他们都很高兴。阳光明媚,鸟儿歌唱,鲜花盛开,他们的魔药课老师斯奈普教授一如既往地闷闷不乐。由于对自己生活的失望加剧了他的焦虑,他在魔药课上给他们布置了很多作业。
n 名学生中的每人都被分配了一项任务。有些学生比其他学生更快地完成某些任务。因此,他们希望重新分配任务,以便每个学生仍然只完成一项任务,并且完成所有任务。每个学生都有自己的懒惰程度,每个任务都有自己的难度级别。 Snipe教授努力提高他们的职业道德,因此每个学生的懒惰程度等于他们任务的难度程度。两组值均由序列 a 给出,其中 ai 代表第 i 个学生的懒惰程度及其任务的难度。
学生完成任务所需的时间等于他们的懒惰程度和任务难度的乘积。他们想知道,如果以最佳方式分配任务,完成所有任务所需的最少总时间是多少。每个人都应该接受一项任务,并且每项任务都应该分配给一个人。打印以 10 007 为模的答案。
输入
输入的第一行包含整数 n (1 ≤ n ≤ 100 000) — 任务数。接下来的 n 行恰好包含一个整数 ai (1 ≤ ai ≤ 100 000)——既是初始任务的难度,也是第 i 个学生的懒惰程度。
输出
打印完成所有任务的最短总时间,以 10 007 为模。
示例
输入 #1
2 1 3
输出 #1
6
注意
在第一个示例中,如果学生切换任务,他们将能够在 3 + 3 = 6 时间单位内完成任务。