Informatica Online Judge

  계단 오르기 [0380 / 017C]

Time Limit(Test case) : 1500(ms)
Number of users who solved : 49   Total Tried : 616


The Champion of this Problem (C++) : gs13057 - 0ms / 446byte
My Best Submission (C++) : N/A

[]

Background

teram 은 계단을 오르는 방법의 수를 알고 싶어졌다. 계단은 총 N단으로 구성되며, k(1<=k<=n)단째의 단의 높이는 Hk (mm)이다. teram 은 계단의 합이 P(mm)이하인 단은 한 번에 오를 수 있다. 계단을 오를 때 같은 단에서 헛걸음 하는 경우는 없으며, 사용한 단이 같은 경우에는 동일한 오르는 방법으로 취급한다. (오를 수 있는 높이가 달라도 같은 단을 밟게 되는 경우를 의미함)

계단의 수 N과 한 번에 오를 수 있는 최대 점프력 P와 각 계단의 높이가 주어질 때 계단의 오르는 방법의 수를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 N( 1 <= N <= 500,000 ) , P( 1 <= P <= 500,000,000 )가 공백으로 구분되어 입력된다.

다음 줄부터 N 개의 Hk 가 한 줄에 하나씩 입력된다.

Output

계단을 오를 수 있는 방법의 수를 1,234,567로 나눈 나머지를 출력하시오.

IO Example

입력
6 350
315
191
98
70
126
200

출력
9


설명) 이 경우에 오를 수 있는 방법은
- 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가지가 존재한다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]