Sum of Subsequences

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

A subsequence is formed by choosing one or more positions from the sequence. Different choices of positions count separately, even if their values are the same.

The first line contains two integers N and S.

• 1 <= N <= 20
• |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 non-empty subsequences whose sum is S.