問題文

N 個の整数 A_1, A_2, \cdots, A_N から 1 個以上を選ぶ方法は 2^N - 1 通りあります。

これらについて、「選んだ整数の最大値」をすべて足した値はいくつになりますか。答えを 1000000007 で割った余りを出力してください。

制約

• 1 \leq N \leq 300000
• 1 \leq A_1 < A_2 < ... < A_N \leq 10^9
• 入力はすべて整数

入力例 1

2
3 5

出力例 1

13

\{ 3 \}、\{ 5 \}、\{ 3, 5 \} の 3 通りの選び方があるため、答えは 3+5+5=13 です。