Competitions

# Pluses and asterisks – 2

Given a sequence of integers a1 ? a2 ? a3 ? … ? an 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 ai and required result respectively. The second line contains space-separated values a1, a2, a3, …, an (3n36, 1r242, 1ak217).

Output

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

Time limit 4 seconds
Memory limit 64 MiB
Input example #1
2 4
2 2

Output example #1
2


Example description: The five ways are: 2+2+2+2; 2+2+2*2; 2+2*2+2; 2*2+2+2; 2*2+2*2.

Source 2014 ACM-ICPC Ukraine, 2nd Round Ukraine, September 13, Problem B