Once upon a time, in a small village at the foot of a mountain, there was a blacksmith named Jack. He was famous throughout the region for crafting weapons with perfect durability and sharpness. One day, he received a request from the king of the kingdom to prepare a large quantity of weapons for the army in defense of the upcoming winter.

Jack has ~n~ types of rare iron ores, each with a different weight, and he can melt a maximum of ~m~ kg of ores at a time in his forge. It is known that each different combination of ores results in a different product. Jack wants to find all possible ways to select ores to put into the forge, such that the total weight of the selected ores does not exceed ~m~ kg. Notably, each type of ore can only be selected once.

Jack is very meticulous and wants to ensure that no combination is missed. He hopes that you, with your mathematical talent, can help him count all the ways to choose the ores such that the total weight is within the allowed limit.

Task:

Help Jack compute the number of ways to choose different types of ores such that their total weight does not exceed ~m~ kg. Since the number of ways may be very large, return the result modulo ~10^9 + 7~.

Input:

• The first line contains two integers ~n~ and ~m~ (~n, m \leq 1000~).
• The second line contains ~n~ integers ~a_1, a_2, ..., a_n~ (~a_i \leq 1000~), representing the weight of each ore type.

Output:

• A single integer: the number of ways to choose ores such that their total weight does not exceed ~m~ kg, modulo ~10^9 + 7~.

Sample Input

2 16
9 7

Sample Output

4

Notes

Jack can melt ores as follows:

• Way ~1: 9~
• Way ~2: 7~
• Way ~3: 9 \to 7~
• Way ~4: 7 \to 9~

Constraints:

• Subtask ~1~ (~30\%~ of points): ~n \leq 6~
• Subtask ~2~ (~30\%~ of points): ~n \leq 20~
• Subtask ~3~ (~40\%~ of points): No additional constraints.