Плюсы и звездочки – 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 ≤ n ≤ 36, 1 ≤ r ≤ 2^42, 1 ≤ a_k ≤ 2^17).

Выходные данные

Вывести одно число - количество способов, которыми можно получить значение r.

Примеры