부분합 카운팅

N개의 정수로 이루어진 수열이 주어진다. 합이 S가 되는 비어있지 않은 부분수열의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 주어진다. (각 값의 절댓값 ≤ 100,000)

출력

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

입출력 예시

입력 1

5 0
-7 -3 -2 5 8

출력 1

1