출고 무게 맞추기

문제

물류 창고에는 출고를 기다리는 상자 N개가 한 줄로 놓여 있다. 상자에는 왼쪽부터 1번부터 N번까지 번호가 붙어 있으며, i번 상자의 무게는 정수 W_i다. 작업자는 이 상자들 중 일부를 골라 하나의 출고 묶음을 만들려고 한다. 운송 장비에 등록한 목표 무게는 T이며, 선택한 상자들의 무게 합이 정확히 T인 묶음만 출고할 수 있다. 각 상자는 선택하거나 선택하지 않을 수 있으며, 하나의 묶음에서 같은 상자를 두 번 사용할 수 없다. 상자를 잘라 무게를 나누거나 다른 물건을 추가하는 작업도 허용하지 않는다. 상자를 고른 순서는 묶음을 구분하는 기준이 아니다. 예를 들어 같은 두 상자를 서로 다른 순서로 고르더라도 하나의 묶음으로 센다. 반면 무게가 같은 상자라도 번호가 다르면 서로 다른 상자다. 따라서 선택한 상자 번호의 집합이 다르면 별개의 묶음으로 센다. 창고에서는 출고 가능한 묶음을 실제로 포장하기 전에 가능한 선택의 수를 확인하려 한다. 목표 무게와 각 상자의 무게를 보고, 조건에 맞는 서로 다른 묶음의 개수를 구해야 한다. 상자를 하나도 선택하지 않은 빈 묶음의 무게 합은 0이다. 빈 묶음도 하나의 선택이므로 T가 0이면 이를 포함해야 한다. 모든 상자의 무게는 양수이므로 상자를 추가했을 때 무게 합이 줄어드는 일은 없다. 입력에 주어진 모든 상자를 반드시 사용할 필요는 없다. 또한 무게 합이 목표를 넘지 않는 묶음의 수를 세는 것이 아니라, 목표와 정확히 같은 묶음의 수를 세어야 한다. 조건을 만족하는 선택이 없으면 정답은 0이다. 정답을 어떤 수로 나눈 나머지를 구하지 않으며, 가능한 묶음의 개수를 그대로 출력한다.

입력

첫째 줄에 정수 N과 T가 공백으로 주어진다. 1 ≤ N ≤ 20, 0 ≤ T ≤ 1,000,000,000이다.
둘째 줄에 정수 W_1, ..., W_N이 공백으로 주어진다. 1 ≤ W_i ≤ 100,000,000이다.

출력

무게 합이 정확히 T인 서로 다른 상자 선택의 개수를 정수 하나로 출력한다. 가능한 선택이 없으면 0을 출력한다.

5 7
1 2 3 4 7

3

3 4
2 2 2

3

1 0
8

1

출처: Devin.KR 자체 제작