Задания прошлых чемпионатов

"D" Разбиение на команды / Разогревочный раунд RCC 2016
Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт

Доктор Эмметт Браун устроился работать преподавателем информатики в школе. В классе, в котором он преподает в этом году, учится n школьников. Доктор Браун хочет провести олимпиаду по программированию среди школьников своего класса. В классе информатики всего k компьютеров, поэтому соревнование придется сделать командным.

Командную олимпиаду писать интересно, если все участники команды имеют примерно одинаковый навык решения задач. Про каждого школьника Эмметт Браун знает ai — его навык решения задач. Было решено разбить школьников на команды таким образом, что для любых двух команд можно найти такое число x, что навыки всех школьников из одной команды не больше, чем x, а навыки всех школьников другой команды — не меньше, чем x. Чтобы компьютеры не простаивали, в каждой команде должен быть хотя бы один человек, но ограничения сверху на количество человек в команде нет.

Помогите доктору посчитать, сколько существует способов разбить учеников на команды. Два разбиения считаются различными, если есть два ученика, которые в одном разбиении участвуют в одной команде, а в другом разбиении — в разных. Поскольку это число может быть достаточно большим, найдите остаток от его деления на число 109 + 7.

Формат входных данных

В первой строке дано два целых числа n, k (1 ≤ n, k ≤ 2 000) — количество учеников в классе и количество команд, на которые их нужно разбить.

Во второй строке дано n целых чисел ai (1 ≤ ai ≤ n) — навык решения задач i-го ученика.

Формат выходных данных

Выведите одно целое число — количество способов разбить учеников на команды по модулю 109 + 7.

Примеры
Входные данные
3 2
1 2 3
Выходные данные
2
Входные данные
7 3
2 4 3 4 3 3 2
Выходные данные
53
 

Вход

ВКонтакте Facebook

Забыли пароль?

Регистрация

На вашу электронную почту была
отправлена инструкция по восстановлению пароля.