Задача №2970. Равенство
Андрей Сергеевич — учитель математики в начальной школе. Вчера на уроке он записал на доске выражение вида
a1 ? a2 ? ... ? aN - 1 ? aN = S
и попросил детей заменить вопросительные знаки на знаки сложения и умножения так, чтобы получилось верное равенство. Разумеется, дети быстро справились с заданием. Особенно понравилось Андрею Сергеевичу то, что мальчик Петя нашел сразу два варианта расстановки знаков. Тогда он попросил класс посчитать, сколько всего существует вариантов правильной расстановки знаков. Напишите программу, которая решает данную задачу.
В первой строке содержится число N (1 ≤ N ≤ 30) — количество чисел в левой части равенства, записанного на доске и число S, записанное в правой части равенства (1 ≤ S ≤ 106). В следующей строке даны N целых чисел в том порядке, в каком они были выписаны на доске. Все числа неотрицательные и не превышают 106.
Выведете на экран одно число –— количество различных вариантов расстановки знаков между числами, приводящих к правильному результату в записанном на доске выражении.
2 4 2 2
2
2 46 4 6
0
4 8 2 2 2 2
5