Reach Target Balance

Given a set of integer transaction amounts, some positive and some negative, determine whether any subset (possibly empty) sums to exactly the target; output 1 if one exists, otherwise 0.

输入格式

The first line contains integers n and target, followed by a line of n integers (this line may be empty when n=0). Site constraints: 0≤n≤40, |target|≤10^12, |transaction[i]|≤10^9. Each transaction can be chosen at most once.

输出格式

Output a single integer: 1 if a qualifying subset exists, otherwise 0. The sum of the empty subset is 0.

样例 1

输入：

3 5
1 2 3

输出：

1

样例 2

输入：

2 4
1 2

输出：

0

样例说明

Decide according to the definition of subset sum; to support transaction amounts with large absolute values, this site sets the missing size bound to n≤40, so meet-in-the-middle can be used.