A treasure chest holds n items, each with a positive integer weight. Items are distinct objects even if two of them happen to weigh the same. Count how many subsets of the items have a total weight exactly equal to a target T.
The empty subset has total weight 0. Two subsets are different if they use a different set of item positions.
Input format
Line 1: two integers n and T.
Line 2: n space-separated positive integers, the item weights.
Output format
A single integer: the number of subsets whose weights sum to exactly T.
Constraints
- 1 <= n <= 18
- 1 <= each weight <= 1000
- 0 <= T <= 20000