Max has a number of coins and wants to know how many ways he can use some or all of the coins to reach a target value. Can you write a program to help him out?

Input Specification

The first line of input will contain two space separated positive integers, ~n~ ~(n \le 15)~, the number of coins Max has, and ~t~ ~(t \le 10^6)~, the target value he wants to reach. The second line of input will contain ~n~ space separated positive integers, ~a_1~ through ~a_n~, where ~a_i~ ~(a_i \le 5 \times 10^5)~ is the value of the ~i^\text{th}~ coin.

Output Specification

Output a single integer on a line by itself, representing the number of ways Max can combine his coins to reach his target value.

Sample Input 1

6 20
3 10 4 7 3 6

Sample Output 1

6

Sample Input 2

10 3500
1000 500 750 250 100 800 1200 900 1300 3000

Sample Output 2

9