Автор задачи и разработчик: Даниил Орешников

Для решения этой задачи достаточно переформулировать ее в терминах сочетаний. Если $$$C_a^b$$$ — число способов выбрать $$$b$$$ элементов из $$$a$$$ различных, то ответом на задачу будет $$$$$$\sum\limits_{t=0}^k C_k^t \cdot C_{k-t}^{n-2t}$$$$$$

Действительно, нам надо выбрать на $$$n$$$ мест различными способоми какие виды лемуров будут представлены двумя лемурами, а какие — одним. Переберем количество «пар» лемуров $$$t$$$. Для фиксированного $$$t$$$: выбрать $$$t$$$ пар можно $$$C_k^t$$$ способами, а на оставшиеся $$$n-2t$$$ места надо разместить по одному лемуру из некоторых из оставшихся $$$k-t$$$ видов.

Теперь вспомним, что $$$C_n^k = \frac{n!}{k!(n-k)!}$$$ (где $$$x!$$$ — произведение всех чисел от $$$1$$$ до $$$x$$$. Пользуясь модульной арифметикой, предподсчитаем $$$\mathtt{frac[i]} = i!~\mathrm{mod}~M$$$ (где за $$$M$$$ обозначен простой модуль $$$10^9+7$$$) как $$$\mathtt{frac}[i+1] = \mathtt{frac}[i] \cdot (i+1)~\mathrm{mod}~M$$$.

Чтобы реализовать деление, воспользуемся расширенным алгоритмом Евклида для нахождения обратного по простому модулю и запомним все обратные к факториалам, после чего $$$C_n^k$$$ можно считать за $$$\mathcal{O}(1)$$$, используя предподсчитанные значения факториалов и обратных к ним величин по модулю $$$M$$$. Суммарное время работы — $$$\mathcal{O}(n \log{n})$$$ на предподсчет (при этом $$$\log$$$ — достаточно завышенная оценка) и $$$\mathcal{O}(n)$$$ на вычисление ответа.