Combinaciones de dados

Se tiene un sistema monetario formado por n monedas. Cada moneda tiene un valor entero positivo. Tu tarea es calcular la cantidad de formas distintas de obtener una suma x utilizando las monedas disponibles.

Por ejemplo, si las monedas son {2,3,5} y la suma deseada es 9, existen 8 formas:

• \(2+2+5\)
• \(2+5+2\)
• \(5+2+2\)
• \(3+3+3\)
• \(2+2+2+3\)
• \(2+2+3+2\)
• \(2+3+2+2\)
• \(3+2+2+2\)

Entrada

La primera línea de entrada contiene dos enteros n y x: la cantidad de monedas y la suma deseada (\(1\leq n\leq 100\), \(1 \leq x \leq 10^6\)).

La segunda línea contiene n enteros distintos \(c_1,c_2,\dots,c_n\): el valor de cada moneda (\(1 \leq c_i \leq 10^6\) para cada \(1 \leq i \leq n\)).

Salida

Imprime un único entero: la cantidad de formas módulo \(10^9+7\).

Ejemplo

Entrada

3 9
2 3 5

Salida

8