계단 (Stairs)

계단을 오르는 방법이 몇 가지인지 알고 싶어졌다. 계단은 N개의 단으로 이루어져 있고, k(1 ≤ k ≤ N)번째 단의 높이 차는 hk mm이다.

너는 높이 차의 합이 P mm 이하인 단들을 한 번에 오를 수 있다. 계단을 오를 때 같은 단에서 발을 구르거나 내려가지는 않는다. 또한 사용한 단이 같으면 같은 오르는 방법으로 본다.

계단을 오르는 방법의 수를 1234567로 나눈 나머지를 구하시오.

표준 입력에서 다음 입력을 읽는다.

• 1번째 줄에는 정수 N과 P가 공백으로 구분되어 쓰여 있다.
• 이어지는 N개의 줄 중 k번째 줄에는 정수 hk가 쓰여 있다.

표준 출력에 다음 데이터를 출력하시오.

• 1번째 줄에는 계단을 오르는 방법의 수를 1234567로 나눈 나머지를 나타내는 정수 하나를 포함해야 한다.

• 1 ≤ N ≤ 500, 000, 계단의 단 수
• 1 ≤ P ≤ 500, 000, 000, 점프력
• 1 ≤ hk, k번째 단의 높이 차
• h1 + … + hN ≤ 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으로 나타낸다.