A lockbox is opened by dialing n numbers, each preceded by a plus or a minus sign. Every number must be given exactly one sign. Given the n non-negative numbers and a target D (which may be negative), count how many of the 2^n sign assignments make the resulting signed sum equal exactly D. Distinct sign patterns are counted separately even when numbers repeat.
Input format
Line 1: two integers n and D.
Line 2: n space-separated non-negative integers.
Output format
A single integer: the number of sign assignments whose signed sum equals D.
Constraints
- 1 <= n <= 40
- 0 <= each number <= 1000
- -40000 <= D <= 40000
- The answer fits in a 64-bit signed integer.