Given a sequence of integers \textbf{a_1} ? \textbf{a_2} ? \textbf{a_3} ? … ? \textbf{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. \textbf{2} + \textbf{2} * \textbf{2} is \textbf{6}, not \textbf{8}. In how many ways it is possible to make result equal to \textbf{r}? \InputFile The first line contains space-separated integers \textbf{n} and \textbf{r}, denoting number of values \textbf{a_i} and required result respectively. The second line contains space-separated values \textbf{a_1}, \textbf{a_2}, \textbf{a_3}, …, \textbf{a_n} (\textbf{3} ≤ \textbf{n} ≤ \textbf{36}, \textbf{1} ≤ \textbf{r} ≤ \textbf{2^42}, \textbf{1} ≤ \textbf{a_k} ≤ \textbf{2^17}). \OutputFile Your program should write exactly one integer - the number of ways to obtain exactly \textbf{r}.