Given an array ~A~ of ~n~ integers, count the number of non-empty subsets whose sum is equal to the given integer ~k~

Input

• The first line is ~2~ integers ~n~, ~k~. ~(n \le 20, |k|\le 100)~
• The second line is the ~n~ integers of the array. ~(|A_i| \le 100)~

Output

• Number of subsets that satisfy the requirement

Example Input 1

4 3
-1 1 1 2

Example Output 1

3