A. Сколько подмножеств даёт сумму

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

Разминка: задача решается и обычной динамикой по суммам, но здесь мы намеренно перебираем маски — чтобы поставить руку.

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

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