Сколько наборов даёт ровно столько

Даны веса $n$ предметов. Посчитайте, сколько подмножеств имеют суммарный вес ровно $S$.

В первой строке $n$ и $S$ ($1 \le n \le 36$, $0 \le S \le 10^{15}$). Во второй — $n$ чисел $w_i$ ($1 \le w_i \le 10^{12}$).

Выведите количество подмножеств с суммой ровно $S$.