Вам надано масив із \(n\) чисел.

Скількома способами можна вибрати підмножину чисел із сумою \(x\)?

Обмеження

• \(1≤n≤40\)
• \(1≤x≤10^9\)
• \(1≤t_i ​ ≤10^9\)

Формат вхідних даних

У першому рядку вхідних даних є два числа \(n\) і \(x\): розмір масиву та шукана сума.

У другому рядку є \(n\) цілих чисел \(t_1 ​ ,t_2 ​ ,…,t_n\) ​ : числа в масиві.

Формат вихідних даних

Виведіть кількість способів, якими можна отримати суму \(x\).

Приклад вхідних даних

4 5
1 2 3 2

Приклад вихідних даних

3