リアルイベント問題セットのアイコン
十億連勝 (paizaランク S 相当)

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!

問題

Img 04 03 下記の問題をプログラミングしてみよう!

あなたは、ゲーム会社 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 と答えてください。

入力される値

入力は以下のフォーマットで与えられます。

N X
A_1
A_2
...
A_N

・1 行目に、ゲームのステージを表す整数 N と、隠し要素の条件を表す整数 X がこの順に半角スペース区切りで与えられます。
・続く N 行のうちの i 行目 (1 ≦ i ≦ N) には、i 番目のステージでの試合数を表す整数 A_i が与えられます。
・入力は合計で N + 1 行となり、入力値最終行の末尾に改行が 1 つ入ります。


入力値最終行の末尾に改行が1つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
期待する出力

隠し要素の条件を満たすようにゲームをプレイしていく方法の通り数の下 9 桁を、整数で出力してください。

条件

すべてのテストケースにおいて、以下の条件をみたします。

・1 ≦ N ≦ 4,000
・0 ≦ X ≦ 1,000,000,000
・0 ≦ A_i ≦ 1,000,000,000 (1 ≦ i ≦ N)

入力例1

3 4
3
2
3

出力例1

7

入力例2

5 1
1
1
1
1
1

出力例2

12

入力例3

14 6
8
5
9
7
6
9
0
9
8
2
8
1
4
10

出力例3

247159393

問題一覧へ戻る

ページの先頭へ戻る