在宇宙大帝 Luke 的星球 Lu3KO5 上，有一所著名的星际学院，专门培养年轻的星际探险家们。在这一天，Luke 亲自担任数学导师，为这些年轻学员们组织了一场有趣的课堂活动。
Luke 让他的学生们站成一排，一共有 n 位学员。每位学员将随意选择一个代表他们能力值的数字 A[i]。接着，Luke 提出了一项挑战：在这些学员中，可以任意选择两名学员，并将他们之间的所有学员作为一个小组（包括这两名学员）。小组中的每个人所拿到的数字之和被称为该小组的“总分数”。
现在，Luke 想知道，如果将所有可能的小组都计算一遍，他们的“总分数之和”会是多少。由于结果可能非常庞大，请你帮助他计算这个结果对 1000000007 取模后的值。
第一行输入一个非负整数 n
第二行输入 n 个非负整数，表示 A[i]
3 1 2 3
20
对于前 30\% 的数据 1 \le n \le 100
对于前 60\% 的数据 1 \le n \le 1000
对于 100\% 的数据 1 \le n \le 10^7, 0 \le A[i] \le 50000