Pluses and asterisks – 2

Given a sequence of integers a_1 ? a_2 ? a_3 ? … ? 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 6, not 8. In how many ways it is possible to make result equal to r?

Input

The first line contains space-separated integers n and r, 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 ≤ n ≤ 36, 1 ≤ r ≤ 2^42, 1 ≤ a_k ≤ 2^17).

Output

Your program should write exactly one integer - the number of ways to obtain exactly r.

Examples