Stairs

You want to find out how many ways there are to climb a staircase. The staircase has N steps, and the height difference of step k (1 ≤ k ≤ N) is hk mm.

You can climb steps in one go as long as the sum of their height differences is at most P mm. While climbing, you do not step in place on the same step or go down. Two climbing ways count as the same when they use the same steps.

Find the number of ways to climb the staircase modulo 1234567.

Read the following input from standard input.

• The first line contains the integers N and P separated by a space.
• The kth of the following N lines contains the integer hk.

Write the following data to standard output.

• The first line must contain one integer, the number of ways to climb the staircase modulo 1234567.

• 1 ≤ N ≤ 500, 000, the number of steps
• 1 ≤ P ≤ 500, 000, 000, your jump power
• 1 ≤ hk, the height difference of step k
• h1 + … + hN ≤ 500, 000, 000

This staircase has 6 steps, and the climbing ways are

• 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 ways in total. For example, the way that uses steps 1, 3, and 5 to reach step 6 is written as 1, 3, 5, 6.