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

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

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

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

입력

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

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

출력

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

제한 사항

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

예제 입력 1

4 3
8 -5 1 2

예제 출력 1

2

예제 설명 1

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

8 -5
1 2