쉬어 가는 시럽 선반

문제

카페에서는 손님이 직접 고른 시럽으로 시음용 음료를 만든다. 선반에는 N개의 시럽 병이 왼쪽부터 1번부터 N번까지 차례로 놓여 있다. 각 병에는 그 시럽을 한 번 넣었을 때 더해지는 단맛 점수가 적혀 있다. 직원은 사용할 병을 먼저 모두 고른 다음, 고른 병마다 시럽을 정확히 한 번씩 넣는다. 한 병을 두 번 이상 고를 수는 없다. 이 선반의 펌프는 서로 가까이 붙어 있다. 두 병의 번호 차이가 1이면 두 펌프를 함께 사용하기 불편하므로, 이웃한 두 병을 동시에 고르는 것은 금지한다. 예를 들어 2번과 4번은 함께 고를 수 있지만 2번과 3번은 함께 고를 수 없다. 1번과 N번은 선반의 양 끝에 있으므로, N이 3 이상일 때 이 두 병은 이웃하지 않는다. 오늘 만들 음료의 목표 단맛 점수는 T다. 고른 모든 병의 단맛 점수를 더한 값이 정확히 T가 되어야 한다. 단맛 점수는 모두 양의 정수이며, 고르는 병의 개수에는 별도의 제한이 없다. 아무 병도 고르지 않는 선택도 허용하고, 이때 단맛 점수의 합은 0이다. 병에 적힌 점수가 같아도 번호가 다르면 서로 다른 병이다. 두 선택에 포함된 병 번호의 집합이 다르면 서로 다른 선택으로 센다. 반면 같은 병들을 서로 다른 순서로 고르는 것은 하나의 선택이다. 직원은 왼쪽 병부터 사용 여부를 결정하며 가능한 선택을 살펴보려고 한다. 이웃한 병을 함께 고르지 않으면서 목표 단맛 점수를 만드는 선택의 수를 구해야 한다. 가능한 선택이 하나도 없으면 그 수는 0이다.

입력

첫째 줄에 정수 N과 T가 공백으로 주어진다. 1 ≤ N ≤ 18, 0 ≤ T ≤ 180이다.
둘째 줄에 각 병의 단맛 점수 A1, A2, …, AN이 공백으로 주어진다. 모든 Ai는 정수이며 1 ≤ Ai ≤ 10이다.

출력

조건을 만족하는 서로 다른 선택의 수를 정수 하나로 출력한다.

5 4
2 2 2 2 2

6

3 0
3 1 3

1

2 5
2 3

0

출처: Devin.KR 자체 제작