L. Сколько наборов попадает в отрезок

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

Первая задача занятия на встречу посередине — и самая простая: здесь надо не искать оптимум, а считать.

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

Выведите количество подмножеств с суммой в отрезке $[L, R]$.