부분 수열의 합 (백트래킹)

N개의 자연수가 주어진다. 합이 정확히 S인 부분 집합의 개수를 구하라. 공집합은 제외한다.

백트래킹으로 탐색하되, 현재까지의 합이 S를 초과하면 가지치기한다.

입력

첫째 줄에 N과 S가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 20, 1 ≤ S ≤ 1,000,000)

둘째 줄에 N개의 자연수가 공백으로 구분되어 주어진다. (1 ≤ 각 수 ≤ 100,000)

출력

합이 S인 부분 집합의 개수를 출력하라.

예제 입력 1

5 10
1 2 3 4 5

예제 출력 1

3