A numismatist owns n coins, each with a whole-number face value (values may repeat). Count the number of subsets of coins whose face values add up to exactly T. Two subsets are different if they consist of a different set of coin positions, even when the multisets of values look the same. The empty subset sums to 0.
Input format
Line 1: two integers n and T.
Line 2: n space-separated integers, the coin face values.
Output format
A single integer: the number of coin subsets summing to exactly T.
Constraints
- 1 <= n <= 40
- 1 <= each face value <= 1000
- 0 <= T <= 40000
- The answer fits in a 64-bit signed integer.