题目描述

$\red{TeaLand }$上的大厨小 $\red{T }$会做 $\red{n }$种汤，每种汤都有一个美味度 $\red{a_i}$，而将两种汤 $\red{i,j }$混合在一起后可以获得 $\red{a_i\times a_j }$的美味度。

所有的顾客都想让小 $\red{T }$混合出最美味的汤，然而小 $\red{T }$已经厌烦了。

现在，小 $\red{T }$会等概率地做这 $\red{n }$种汤的一种，然后再随机做一种，这样就会有两碗汤 $\red{i,j }$（注意 $\red{i=j }$是允许的） 。

小 $\red{T }$想知道新的这碗汤的期望美味度对 $\red{10^9+7 }$的取莫结果是多少。

期望是对于某个随机变量的加权平均，例如，如果 $\red{X }$有 $\red{30\%}$的概率为 $\red{1}$，$\red{30\%}$ 的概率为 $\red{2}$，$\red{40\%}$ 的概率为 $\red{3}$

，那么 $\red{X }$的期望值是 $\red{30\%\times 1+30\%\times 2+40\%\times 3=2.1}$。

对于有理数 $\red{\frac ab }$取莫，只需要计算出 $\red{a\times c }$在莫意义下的结果，其中 $\red{c }$满足 $\red{b\times c }$在莫意义下等于 $\red{1}$

。

输入格式

第一行一个正整数 $\red{n}$。

之后一行 $\red{n }$个正整数 $\red{a_i}$。

输出格式

输出一行一个整数，表示期望美味值对 $\red{10^9+7 }$的取莫结果。

样例

输入样例

3
1 2 3

输出样例

4

提示

对于 $\red{40\%}$ 的数据，保证 $\red{n\le10^3}$。

对于所有的数据，保证 $\red{1\le n\le10^6}$，$\red{1\le a_i\le 10^9}$。