10039 부분집합의 합 Silver III

문제

N개의 자연수로 이루어진 집합에서, 원소의 합이 S가 되는 부분집합의 개수를 구하는 프로그램을 작성하시오. 공집합은 제외한다.

입력

첫째 줄에 N (1 ≤ N ≤ 20)과 S (1 ≤ S ≤ 10,000,000)가 주어진다. 둘째 줄에 N개의 자연수가 공백으로 구분되어 주어진다. 각 수는 1 이상 1,000,000 이하이다.

출력

합이 S가 되는 부분집합의 개수를 출력한다.

5 9
1 2 3 4 5

3