수열 축소

N개의 양의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에는 인접한 두 원소를 하나로 합치는 축소 연산이 정의되어 있다. 축소 연산 CON(A, i)는 A[i]를 A[i] - A[i+1]로 바꾸고 A[i+1]을 수열에서 제거한다. 그 결과 수열은 다음과 같아진다.

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

연산을 한 번 적용할 때마다 수열의 길이가 1씩 줄어들며, N-1번 적용하면 수열에는 단 하나의 수만 남는다.

예를 들어 수열 {12, 10, 4, 3, 5}에 다음 순서로 축소 연산을 적용하면 마지막에 4가 남는다.

• 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}

수열 A와 목표 값 T가 주어질 때, 축소 연산을 적절한 순서로 적용하여 마지막에 남는 수를 정확히 T로 만들 수 있는지 판별하는 프로그램을 작성하시오.

첫째 줄에 수열의 길이 N (1 ≤ N ≤ 100)과 목표 값 T (0 ≤ |T| ≤ 10,000)가 공백으로 구분되어 주어진다. 둘째 줄에 수열의 원소 A[1], A[2], …, A[N]이 공백으로 구분되어 주어진다. 각 A[i]는 1 이상 100 이하의 정수이다.

축소 연산을 적절히 적용하여 마지막에 남는 수를 T로 만들 수 있으면 1을, 만들 수 없으면 0을 출력한다.