SoftwareTester2

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

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

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

• 入力はすべて整数である。

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

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

2
2 3

21

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

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

1
100

5050

4
1000000000 1000000000 1000000000 1000000000

999971195

答えを で割ったあまりを出力してください。