A君はソフトウェアテストのテストを行います。テスト対象の機能には個のパラメータがあり、番目のパラメータは~の通りの値を持つことができます。
テストでは全てのパラメータのパターンを試す必要がありますが、A君が試すことになるテストケースはいくつになるでしょうか?
答えは非常に大きくなる可能性があるため、で割ったあまりを答えてください。
入力は以下の形式で標準入力から与えられる。
...
A君が行うことになるテストケースの個数を出力せよ。
2 2 3
6
テストするパラメータは組み合わせはの通りになります。 よって答えはです。
1 100
100
4 1000000000 1000000000 1000000000 1000000000
2401
答えを で割ったあまりを出力してください。