정수 \(n\)개가 주어진다.

이 정수들 중 일부를 골라 합이 정확히 \(k\)가 되도록 하는 부분집합의 개수를 구하시오.

이번 문제에서는 음인 정수가 주어지지 않는다.

아무 원소도 고르지 않는 경우도 하나의 부분집합으로 센다.

같은 값을 가진 원소가 여러 개 있어도, 위치가 다르면 서로 다른 원소로 본다.

입력

첫째 줄에 정수의 개수 \(n\)과 목표 합 \(k\)가 공백으로 구분되어 주어진다.

둘째 줄에 \(n\)개의 정수가 공백으로 구분되어 주어진다.

출력

합이 \(k\)가 되는 부분집합의 개수를 출력한다.

제한 사항

• \(1 \le n \le 20\)
• \(0 \le k \le 10,000\)
• \(0 \le a_i \le 1,000\)

예제 입력 1

5 7
1 2 3 4 5

예제 출력 1

3

예제 설명 1

합이 \(7\)이 되는 선택은 다음과 같이 세 가지이다.

2 5
3 4
1 2 4