Stairs(階段) - joi2010-day1

出典: 第9回日本情報オリンピック 春季トレーニング合宿

時間制限: 1.5秒

メモリ制限: 64MB

あなたは, 階段の上り方が何通りあるかを調べたくなった. 階段はN段からなり, k(1 ≤ k ≤ N) 段目の段差はh[k] mm である.

あなたは, 段差の和がP mm 以下の段を一度に上ることができる. 階段を上るときに, 同じ段で足踏みしたり, 下ったりはしない. また, 用いた段が同じ時に同じ上り方とみなす.

課題(TASK)

階段の上り方の場合の数の1234567による余りを求めよ.

制限(CONSTRAINTS)

1 ≤ N ≤ 500,000	階段の段数
1 ≤ P ≤ 500,000,000	ジャンプ力
1 ≤ h[k]	k段目の階段の段差
h1 + … + h[N] ≤ 500,000,000

入力(INPUT)

標準入力から以下の入力を読み込め.

• 1行目には整数NとPが空白を区切りとして書かれている.
• 続くN行のうちのk行目には整数h[k]が書かれている.

出力(OUTPUT)

標準出力に以下のデータを出力せよ.

• 1行目にはあなたの階段の上り方の場合の数の1234567による余りを表す, 1つの整数を含んでいなければならない.

採点基準(GRADING)

50点分のテストグループにおいて, Nは3,000を超えない.

入出力例(EXAMPLE)

入力例(Sample Input)	出力例(Sample Output)
6 350 315 191 98 70 126 200	9

この階段は6段からなり, 上り方は

• 1,2,3,4,5,6
• 1,2,3,4,6
• 1,2,3,5,6
• 1,2,4,5,6
• 1,2,4,6
• 1,2,5,6
• 1,3,4,5,6
• 1,3,4,6
• 1,3,5,6

の9 通りである. ただし, 例えば1段目と3段目と5段目を用いて6段目に上る方法を1,3,5,6と表している．