El personal del ICPC NAC ha escrito una serie de problemas y desea construir un conjunto de problemas a partir de ellos. Cada problema tiene una calificación de dificultad positiva.

Un concurso tiene una distribución de dificultad "agradable" (Nice) si, al ordenar las dificultades de los problemas en orden ascendente, cada problema después del segundo tiene una calificación de dificultad menor o igual a la suma de las calificaciones de dificultad de los dos problemas inmediatamente anteriores a dicho problema.

Dadas las calificaciones de dificultad de un conjunto de problemas y el número de problemas deseados para el conjunto, cuente el número de conjuntos de problemas con distribuciones de dificultad "agradables". Dos conjuntos de problemas son distintos si y solo si hay algún problema en un conjunto que no está en el otro. (Específicamente, tenga en cuenta que dos conjuntos de problemas son iguales incluso si los problemas están permutados).

Entrada

La primera línea de la entrada contiene dos enteros $n$ ($3 \le n \le 50$) y $k$ ($3 \le k \le 18$, $k \le n$), donde $n$ es el número de problemas que los jueces han escrito y $k$ es el número de problemas que desean incluir en el conjunto de problemas.

Cada una de las siguientes $n$ líneas contiene un único entero $d$ ($1 \le d \le 10^9$). Estas son las dificultades de los problemas.

Salida

Imprima un único entero, que es el número de posibles conjuntos de problemas con distribuciones de dificultad "agradables".

Ejemplos

Entrada 1

5 4
2
1
4
3
5

Salida 1

4

Entrada 2

8 5
1
2
3
5
8
13
21
34

Salida 2

4