Problem Description

在宇宙大帝 Luke 的星球 Lu3KO5 上，有一所著名的星际学院，专门培养年轻的星际探险家们。在这一天，Luke 亲自担任数学导师，为这些年轻学员们组织了一场有趣的课堂活动。

Luke 让他的学生们站成一排，一共有 $n$ 位学员。每位学员将随意选择一个代表他们能力值的数字 $A[i]$。接着，Luke 提出了一项挑战：在这些学员中，可以任意选择两名学员，并将他们之间的所有学员作为一个小组（包括这两名学员）。小组中的每个人所拿到的数字之和被称为该小组的“总分数”。

现在，Luke 想知道，如果将所有可能的小组都计算一遍，他们的“总分数之和”会是多少。由于结果可能非常庞大，请你帮助他计算这个结果对 $1000000007$ 取模后的值。

Input Format

第一行输入一个非负整数 $n$

第二行输入 $n$ 个非负整数，表示 $A[i]$

Output Format

输出一个整数，即答案

3
1 2 3

20

82
1088 47343 14108 1512 11947 3299 35956 11141 40476 3341 15851 12436 25672 6089 24355 26864 2267 46150 37682 29181 42171 382 38205 12561 28660 11919 42722 40117 20347 27412 942 44529 12235 44238 12292 26540 5661 17433 30896 31109 29204 10129 15151 44954 24038 49602 23327 46413 27687 32467 217 15944 17671 6658 20160 3119 30068 41311 11279 40994 27908 11884 34836 9689 39144 45016 2264 5390 31821 30962 32967 33745 8423 4635 18812 15296 1061 2733 11825 40730 6479 17110 

248442780

Hint

数据范围

对于前 $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$