24112번 - 階段 (Stairs) 다국어

あなたは，階段の上り方が何通りあるかを調べたくなった．階段は N 段からなり，k(1 ≤ k ≤ N) 段目の 段差は h_k mm である．

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

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

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

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

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

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

• 1 ≤ N ≤ 500, 000 階段の段数
• 1 ≤ P ≤ 500, 000, 000 ジャンプ力
• 1 ≤ h_k k 段目の階段の段差
• h₁ + · · · + h_N ≤ 500, 000, 000

この階段は 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 と表して いる．