L'équipe de l'ICPC NAC a rédigé un certain nombre de problèmes et souhaite en constituer un ensemble. Chaque problème possède une note de difficulté positive.

Un concours a une distribution de difficulté « Nice » si, lorsque les difficultés des problèmes sont triées par ordre croissant, chaque problème après le deuxième a une note de difficulté inférieure ou égale à la somme des notes de difficulté des deux problèmes qui le précèdent immédiatement.

Étant donné les notes de difficulté d'un ensemble de problèmes et le nombre de problèmes souhaités pour l'ensemble, comptez le nombre d'ensembles de problèmes ayant des distributions de difficulté « Nice ». Deux ensembles de problèmes sont distincts si et seulement s'il existe un problème présent dans l'un mais pas dans l'autre. (Notez spécifiquement que deux ensembles de problèmes sont identiques même si les problèmes sont permutés.)

Entrée

La première ligne de l'entrée contient deux entiers $n$ ($3 \le n \le 50$) et $k$ ($3 \le k \le 18$, $k \le n$), où $n$ est le nombre de problèmes rédigés par les juges et $k$ est le nombre de problèmes qu'ils souhaitent inclure dans l'ensemble.

Chacune des $n$ lignes suivantes contient un entier unique $d$ ($1 \le d \le 10^9$). Il s'agit des difficultés des problèmes.

Sortie

Affichez un seul entier, qui représente le nombre d'ensembles de problèmes possibles ayant des distributions de difficulté « Nice ».

Exemples

Entrée 1

5 4
2
1
4
3
5

Sortie 1

4

Entrée 2

8 5
1
2
3
5
8
13
21
34

Sortie 2

4