問題文

B君はソフトウェアのテストを行います。テスト対象の機能には$N$個のパラメータがあり、$i$番目のパラメータは$1$~$P_i$の$P_i$通りの値を持つことができます。

テストでは全てのパラメータのパターンを試す必要があり、1回のテスト実行にかかる時間は選択したパラメータ$N$個の総和秒になります。B君が全てのテストを完了するまでに何秒かかるでしょうか？

答えは非常に大きくなる可能性があるため、$10^9+7$で割ったあまりを答えてください。

制約

• 入力はすべて整数である。
• $1 \leq N \leq 10^5$
• $1 \leq P_i \leq 10^9$

入力

入力は以下の形式で標準入力から与えられる。

出力

B君が全てのテストを完了するまでにかかる秒数を出力せよ。

サンプル

2
2 3

21

テストするパラメータは組み合わせは

• $1+1=2$
• $1+2=3$
• $1+3=4$
• $2+1=3$
• $2+2=4$
• $2+3=5$

であり、これらの総和は$21$となります。よって答えは$21$秒です。

1
100

5050

4
1000000000 1000000000 1000000000 1000000000

999971195

答えを $10^9+7$ で割ったあまりを出力してください。