Subsequence Sum Count 2

Given a sequence of N integers, count how many non-empty subsequences have sum S.

Two selections are different if they choose different positions, even when the selected values are the same.

The first line contains the number of integers N and the target sum S. (1 ≤ N ≤ 40, |S| ≤ 1,000,000)

The second line contains N integers separated by spaces. The absolute value of each integer is at most 100,000.

Print the number of subsequences whose sum is S.