严神又要组队了。 这次他的候选人有 n 人。队伍的大小至少需要 2 人, 至多可包括全部 n 人。
每个人都有一定的能力值 a_i , 一个队伍的能力值为 max(a_i) * min(a_i) , 即等于该队伍中能力最强的值乘以最弱的值. 严神想知道, 所有的队伍选择方法中, 队伍的能力值总和 S 是多少。这个数可能很大, 请模 1000000007 .
输入共 2 行。 第 1 行, 一个整数 n , 代表候选人数。 第 2 行, n 个整数, 代表每个队员的能力值 a_i .
输出仅一行一个数字, 队伍的能力值总和 S mod 1000000007 .
3 1 2 3
14
该样例中, 可以组成的所有队伍为 {1, 2} {1, 3} {2, 3} {1, 2, 3}, 其总和为 1 * 2 + 1 * 3 + 2 * 3 + 1 * 3 = 14.
对于 30% 的数据, n \leq 10^3
对于 100% 的数据, 1 \leq n \leq 10^5, 1 \leq a_i \leq 10^9