Ifri estaba estudiando programación y le dieron ganas de jugar con arreglos. Después de jugar solo todo el día comenzó a aburrirse, así que llamó a su amigo Torvic para que le propusiera algo nuevo. Torvic le planteó el siguiente problema:

Dado un arreglo de ~n~ números, ¿de cuántas formas puedes elegir un subconjunto de este tal que la suma sea ~x~?

Ifri cree que es un problema interesante, así que te llamó también a ti para que te diviertas con él.

Entrada

La primera línea de la entrada tiene dos números: ~n~ ~(1 \leq n \leq 40)~ y ~x~ ~(1 \leq x \leq 10^9)~, el tamaño del arreglo y la suma requerida, respectivamente.

La segunda línea contiene ~n~ enteros ~t_1,t_2,\dots,t_n~ ~(1 \leq t_i \leq 10^9)~: los números en el arreglo.

Salida

El número de formas en que puedes crear la suma ~x~.

Ejemplo de Entrada

4 5
1 2 3 2

Ejemplo de Salida

3