Nguồn : https://cses.fi/problemset/task/1628/ Cho bạn một dãy X gồm n số nguyên. Đếm số cách bạn có thể chọn 1 tập con của X có tổng bằng S.

Input

Dòng 1: Gồm 2 số nguyên n và S (1 ≤ n ≤ 40, ~ 1 ≤ S ≤ 10^9 ~).

Dòng 2: n số ~ a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9) ~ là phần tử của dãy X.

Output

In ra số cách bạn có thể chọn 1 tập con của X có tổng bằng S.

Sample Input

4 5
1 2 3 2

Sample Output

3