# ДОРЕШИВАНИЕ 2014 ACM-ICPC Украина, 2ой Раунд Украина, Сентябрь 13

# Pluses and asterisks – 2

Given a sequence of integers **a _{1}** ?

**a**?

_{2}**a**? … ?

_{3}**a**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.

_{n}**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**.

2 4 2 2

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.