Peter is a football fan. All his life, he dreamed of attending World Cup matches, but tickets were too expensive for his modest budget. Fortunately, this year, for excellent results in school, Peter received an award in the amount of S dollars, which allows him to attend at least a few football matches of this spectacular event. It is known that n matches will be played at the World Cup, which, for educational purposes, are indicated by 1, 2, 3, ... i, ... n. In general, ticket prices for various matches may not match. Let's denote by the ticket price for the i-th match. Peter would like to know the number of all possible ways V to spend his available money by buying tickets to football matches. He is not going to spend all the money or attend a certain number of matches in an obligatory manner.
Task: Write a program that knows the amount of money S, the number of matches n and the cost of tickets 1, 2, ... , , ... , , determines the number of all possible ways V to spend Peter's available money.
Input data: The first line of the standard input contains the integers n and S, separated by a space. The second line of the standard input contains integers 1, 2, ... , , ... , , separated by spaces.
Output data: The single line of the standard output must contain an integer V.
Limitations. 1 ≤ ≤ 40; 1 ≤ ≤ 10^18; ≤ 10^16, = 1, 2, 3, … , . The program execution time should not exceed 0.5 seconds. The program should use no more than 20 Megabytes of RAM
Example: Input: 5 1000 100 1500 500 500 1000 Output: 8
Explanation. Let's denote by M the set containing the numbers i of those matches for which Peter could buy tickets. The set M can have the following values: (Peter does not buy any tickets); {1}; {3}; {4}; {5}; {1, 3}; {1, 4}; {3, 4}, There are 8 options in total
The problem is that I cannot solve this task with bruteforce, due to execution time limit. So there shoud be a way to solve this smarter If I choosed the wrong website for this question, please, recommend me another one