Sum of Subsequences

Time limit

Memory limit

256 MB

Problem

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.

Input

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.

Output

Print the number of non-empty subsequences whose sum is S.