問題文

A君はソフトウェアテストのテストを行います。テスト対象の機能にはNN個のパラメータがあり、ii番目のパラメータは11~PiP_iPiP_i通りの値を持つことができます。

テストでは全てのパラメータのパターンを試す必要がありますが、A君が試すことになるテストケースはいくつになるでしょうか?

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

制約

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

入力

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

NN

P1P_1 P2P_2 ... PNP_N

出力

A君が行うことになるテストケースの個数を出力せよ。

サンプル

入力例1
2
2 3
出力例1
6

テストするパラメータは組み合わせは(1,1),(1,2),(1,3),(2,1),(2,2),(2,3)(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3)66通りになります。 よって答えは66です。


入力例2
1
100
出力例2
100

入力例3
4
1000000000 1000000000 1000000000 1000000000
出力例3
2401

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

提出


Go (1.21)