题目描述

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

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

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

输入格式

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

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

输出格式

输出一个整数，即答案

样例输入 #1

3
1 2 3

样例输出 #1

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$