Плюси і зірочки – 2

Задано послідовність цілих чисел (a_1 ? a_2 ? a_3 ? ...? a_n). Необхідно замінити кожен знак ? на + або * так, щоб вираз обчислювався згідно з арифметичними правилами, де + означає додавання, а * — множення. Множення має вищий пріоритет над додаванням, тобто (2 + 2 * 2) дорівнює (6), а не (8). Потрібно визначити, скількома способами можна отримати результат (r).

Вхідні дані

Перша стрічка містить два числа (n) і (r) — кількість елементів (a_i) та бажаний результат. Друга стрічка містить числа (a_1, a_2, a_3, ..., a_n), розділені пробілами ((3 $\le$ n $\le$ 36), (1 $\le$ r $\le$ 2^42), (1 $\le$ a_k $\le$ 2^17)).

Вихідні дані

Виведіть одне число — кількість способів, якими можна отримати значення (r).

Приклади