• 时间：1s
• 空间：256M

题目描述

数学老师小 Z 课堂上组织大家玩一个小游戏，他一共有 $n$ 位学生，首先请大家站成一排，然后每个人随便选一个数字 $A_i$ 。此时任意选择两名学生，他们之间的学生可以作为一组（包含这两名学生），组内每个人拿到的数字之和便称为这些学生的总分数。求所有组的总分数之和。由于数值较大，结果对 $10^9+7$ 取模。

输入格式

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

第二行输入 $n$ 个非负整数 $A_1,A_2,\cdots,A_n$ 。

输出格式

输出一个非负整数，表示总分数。

样例

输入样例

3
1 2 3

输出样例

20

提示

样例解释

$3$ 个学生，分别选了三个数 $1,2,3$，可能的小组包括：$\{1\}、 \{2\}、 \{3\}、 \{1,2\}、 \{2,3\} 、\{1,2 ,3\}$，这些组的组内分数为 $1,2,3,3,5,6$，这些小组的总分数就是 $20$。

数据范围

$30\%$ 的数据：$n \le 100$ ；

$50\%$ 的数据：$n \le 1000$ ；

$100\%$ 的数据：$n \le 10^5$ ，$0 \le A_i \le 50000$ 。