Zespół ICPC NAC przygotował pewną liczbę zadań i chce stworzyć z nich zestaw zadań. Każde zadanie ma dodatnią ocenę trudności.

Konkurs ma "ładny" (ang. Nice) rozkład trudności, jeśli po posortowaniu trudności zadań w kolejności rosnącej, każde zadanie po drugim ma ocenę trudności mniejszą lub równą sumie ocen trudności dwóch zadań bezpośrednio je poprzedzających.

Mając dane oceny trudności zbioru zadań oraz liczbę zadań, które mają znaleźć się w zestawie, oblicz liczbę zestawów zadań o "ładnym" rozkładzie trudności. Dwa zestawy zadań są różne wtedy i tylko wtedy, gdy istnieje zadanie, które znajduje się w jednym zestawie, a nie ma go w drugim. (W szczególności należy zauważyć, że dwa zestawy zadań są takie same, nawet jeśli zadania w nich są w innej kolejności).

Wejście

Pierwsza linia wejścia zawiera dwie liczby całkowite $n$ ($3 \le n \le 50$) oraz $k$ ($3 \le k \le 18, k \le n$), gdzie $n$ to liczba zadań przygotowanych przez sędziów, a $k$ to liczba zadań, które chcą umieścić w zestawie.

Każda z kolejnych $n$ linii zawiera pojedynczą liczbę całkowitą $d$ ($1 \le d \le 10^9$). Są to trudności zadań.

Wyjście

Wypisz pojedynczą liczbę całkowitą, która jest liczbą możliwych zestawów zadań o "ładnym" rozkładzie trudności.

Przykład

Wejście 1

5 4
2
1
4
3
5

Wyjście 1

4

Wejście 2

8 5
1
2
3
5
8
13
21
34

Wyjście 2

4