Pluses and asterisks – 2#7325
Given a sequence of integers a_1\ ?\ a_2\ ?\ a_3\ ?\ \ldots\ ?\ a_n one may replace each ? with either + or *. After that, the expression is evaluated according to arithmetic rules, where + denotes addition, * denotes multiplication. Multiplication's precedence is higher than addition's, i.e. 2 + 2 * 2 is , not . In how many ways it is possible to make result equal to ?
The first line contains space-separated integers and , denoting number of values a_i and required result respectively. The second line contains space-separated values a_1, a_2, a_3, , a_n (3 \leq n \leq 36, 1 \leq r \leq 2^{42}, 1 \leq a_k \leq 2^{17}).
Your program should write exactly one integer - the number of ways to obtain exactly .
Esempio 1