十億連勝（paizaランク S 相当）

あなたは、ゲーム会社 PAIZA でゲームを作っているエンジニアです。あなたは、今、新しい格闘ゲームを作っています。

あなたが作っているゲームは、N 個のステージからなります。 i 番目 (1 ≦ i ≦ N) のステージでは、A_i 回の試合が行われます。次の図は、入力例 1 の場合のゲームのイメージを表します。



試合の例

ゲームのプレイヤーは、それぞれのステージの試合を順に行っていきます。しかし、ステージの途中で試合に負けた場合、そのステージにまだ残っている試合があっても、強制的に次のステージに進んでしまいます。

たとえば、下の図の例では、1 番目のステージの第 2 試合で負けているので、1 番目のステージの第 3 試合を迎えること無く 2 番目のステージに進んでしまいます。



試合の例

あなたは、このゲームに隠し要素を付けることにしました。その隠し要素とは、「1 番目のステージからはじめ、N 個すべてのステージを終えた時点で、それまでの最大の連勝数がちょうど X だった場合、ボーナスステージが出現する」というものです。

ここで、連勝数とは、連続して勝った試合の数のことを指します。先程の図の場合、最大の連勝数は、第 2 ステージの第 1 試合から第 3 ステージの第 2 試合までで連続して勝っているため、 4 になります。

あなたは、隠し要素の条件を満たすようにゲームをプレイしていく方法が何通りあるかが気になりました。そこで、隠し要素の条件を満たすプレイの仕方の総数をゲームのデバッグ画面に出力することにしました。しかし、デバッグ画面には 9 桁の整数までしか表示することが出来ません。そこで、条件を満たす通り数の下 9 桁を求めてください。

例)

入力例 1 の場合、隠し要素の条件を満たすプレイの仕方の総数は全部で 7 通りあります。これは 9 桁より少ないので、そのまま 7 と答えてください。

入力例 3 の場合、隠し要素の条件を満たすプレイの仕方の総数は全部で 3,247,159,393 通りあります。この場合、下 9 桁である 247159393 と答えてください。