配点 : 500 点
問題文
0,1 からなる長さ N の異なる 2 つの数列 S,T に対し、関数 f(S,T) を以下のように定めます。
- S に対し以下の操作を繰り返して T と等しくすることを考える。このとき行う操作のコストの和として考えられる最小の値が f(S,T) である。
- Si を (0 から 1、もしくは 1 から 0 に) 変更する。この操作のコストは、変更の直前に Sj=Tj(1≤j≤N) であったような整数 j の個数を D として、D×Ci である。
0,1 からなる長さ N の異なる 2 つの数列の組 (S,T) は 2N×(2N−1) 通り考えられます。これらすべてに対する f(S,T) の和を 109+7 で割った余りを計算してください。
制約
- 1≤N≤2×105
- 1≤Ci≤109
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N
C1 C2 ⋯ CN
出力
f(S,T) の和を 109+7 で割った余りを出力せよ。
1
1000000000
999999993
0,1 からなる長さ 1 の異なる 2 つの数列の組 (S,T) は以下の 2 通りが考えられます。
- S=(0),T=(1): S1 を 1 に変更することでコスト 1000000000 で S=T とできるため、f(S,T)=1000000000 です。
- S=(1),T=(0): S1 を 0 に変更することでコスト 1000000000 で S=T とできるため、f(S,T)=1000000000 です。
これらの和は 2000000000 であり、これを 109+7 で割った余りは 999999993 です。
2
5 8
124
0,1 からなる長さ 2 の異なる 2 つの数列の組 (S,T) は 12 通り存在し、例えば以下のものが考えられます。
- S=(0,1),T=(1,0)
この場合、1 回目の操作で S1 を 1 に変更し、2 回目の操作で S2 を 0 に変更するとき、操作のコストの和は 5×2+8=18 です。これより小さいコストで S=T とすることはできないので、f(S,T)=18 です。
5
52 67 72 25 79
269312