H. Максимальное произведение?
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано положительное целое число $$$k$$$. Для мультимножества целых чисел $$$S$$$ определим $$$f(S)$$$ следующим образом:

  • Если количество элементов в $$$S$$$ меньше чем $$$k$$$, то $$$f(S)=0$$$.
  • Иначе определим $$$f(S)$$$ как максимально возможное произведение при выборе ровно $$$k$$$ элементов из $$$S$$$.

Более формально, пусть $$$|S|$$$ означает число элементов в $$$S$$$. Тогда,

  • Если $$$|S|<k$$$, то $$$f(S)=0$$$.
  • Иначе $$$f(S)=\max\limits_{T\subseteq S,|T|=k}\left(\prod\limits_{i\in T}i\right)$$$.

Вам дано мультимножество целых чисел $$$A$$$. Вычислите $$$\sum\limits_{B\subseteq A} f(B)$$$ по модулю $$$10^9+7$$$.

Обратите внимание, что в этой задаче элементы считаются различными, если они имеют различные индексы, но необязательно различные значения. То есть мультимножество, состоящее из $$$n$$$ элементов, всегда содержит $$$2^n$$$ различных подмножеств вне зависимости от того, равны ли в нём какие-то элементы или нет.

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

Первая строка содержит два целых числа $$$n$$$ и $$$k$$$, где $$$n$$$ — количество элементов в $$$A$$$ ($$$1\le k\le n\le 600$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\dots,a_n$$$, задающих элементы $$$A$$$ ($$$-10^9\le a_i\le 10^9$$$).

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

Выведите $$$\sum\limits_{B\subseteq A} f(B)$$$ по модулю $$$10^9+7$$$.

Примеры
Входные данные
3 2
-1 2 4
Выходные данные
10
Входные данные
3 1
1 1 1
Выходные данные
7
Входные данные
10 4
-24 -41 9 -154 -56 14 18 53 -7 120
Выходные данные
225905161
Входные данные
15 5
0 0 2 -2 2 -2 3 -3 -3 4 5 -4 -4 4 5
Выходные данные
18119684
Примечание

Рассмотрим первый тестовый пример. Из определения,

  • $$$f(\varnothing)=0$$$
  • $$$f(\{-1\})=0$$$
  • $$$f(\{2\})=0$$$
  • $$$f(\{4\})=0$$$
  • $$$f(\{-1,2\})=-2$$$
  • $$$f(\{-1,4\})=-4$$$
  • $$$f(\{2,4\})=8$$$
  • $$$f(\{-1,2,4\})=8$$$

Таким образом, вывести необходимо $$$(0+0+0+0-2-4+8+8)\bmod (10^9+7)=10$$$.

Во втором тестовом примере мультимножество, хоть и состоит из трёх равных элементов, содержит $$$8$$$ различных подмножеств: $$$\varnothing,\{1\},\{1\},\{1\},\{1,1\},\{1,1\},\{1,1\},\{1,1,1\}$$$.