Сотрудники ICPC NAC подготовили ряд задач и хотят составить из них набор. Каждая задача имеет положительный рейтинг сложности.

Контест имеет «хорошее» (Nice) распределение сложности, если при сортировке сложностей задач по возрастанию каждая задача, начиная с третьей, имеет рейтинг сложности, не превышающий сумму рейтингов сложности двух непосредственно предшествующих ей задач.

По заданным рейтингам сложности набора задач и требуемому количеству задач в наборе, подсчитайте количество наборов задач с «хорошим» распределением сложности. Два набора задач считаются различными тогда и только тогда, когда существует задача, входящая в один набор, но не входящая в другой. (Заметим, что два набора задач считаются одинаковыми, даже если задачи в них переставлены местами.)

Входные данные

Первая строка входных данных содержит два целых числа $n$ ($3 \le n \le 50$) и $k$ ($3 \le k \le 18, k \le n$), где $n$ — количество задач, подготовленных жюри, а $k$ — количество задач, которые они хотят включить в набор.

Каждая из следующих $n$ строк содержит одно целое число $d$ ($1 \le d \le 10^9$). Это рейтинги сложности задач.

Выходные данные

Выведите единственное целое число — количество возможных наборов задач с «хорошим» распределением сложности.

Примеры

Входные данные 1

5 4
2
1
4
3
5

Выходные данные 1

4

Входные данные 2

8 5
1
2
3
5
8
13
21
34

Выходные данные 2

4