Sequence Reduction

Time limit2sMemory limit128 MB

Summary

Decide if repeatedly merging adjacent elements as A[i]-A[i+1] can reduce the sequence to a single target value T.

Level: Medium5 of 10
Topics: Dynamic programming, Recursion
Solved: No attempts yet

Problem

You are given a sequence of N positive integers A[1], A[2], …, A[N]. A reduction operation that merges two adjacent elements into one is defined on this sequence. The reduction operation CON(A, i) replaces A[i] with A[i] - A[i+1] and removes A[i+1] from the sequence. The result is:

$\mathrm{CON}(A, i) = \{A[1],\ \dots,\ A[i-1],\ A[i] - A[i+1],\ A[i+2],\ \dots,\ A[N]\}$

Each application shortens the sequence by one element, so after N-1 applications exactly one number remains.

For example, applying the reduction operation to the sequence {12, 10, 4, 3, 5} in the following order leaves 4 at the end:

CON({12, 10, 4, 3, 5}, 2) = {12, 6, 3, 5}
CON({12, 6, 3, 5}, 3) = {12, 6, -2}
CON({12, 6, -2}, 2) = {12, 8}
CON({12, 8}, 1) = {4}

Given the sequence A and a target value T, write a program that determines whether the reduction operation can be applied in some order so that the single remaining number is exactly T.

Input

The first line contains the length of the sequence N (1 ≤ N ≤ 100) and the target value T (0 ≤ |T| ≤ 10,000), separated by a space. The second line contains the elements A[1], A[2], …, A[N] separated by spaces. Each A[i] is an integer between 1 and 100 inclusive.

Output

Print 1 if the reduction operation can be applied so that the last remaining number equals T; otherwise print 0.

Examples2

Example 1
Input
```
4 5
10 2 5 2
```
Expected output
```
1
```
Example 2
Input
```
5 8
12 10 4 3 5
```
Expected output
```
1
```