Вам дано положительное целое число \(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\) различных подмножеств вне зависимости от того, равны ли в нём какие-то элементы или нет.
Выходные данные
Выведите \(\sum\limits_{B\subseteq A} f(B)\) по модулю \(10^9+7\).
Примечание
Рассмотрим первый тестовый пример. Из определения,
- \(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\}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
-1 2 4
|
10
|
|
2
|
3 1
1 1 1
|
7
|
|
3
|
10 4
-24 -41 9 -154 -56 14 18 53 -7 120
|
225905161
|
|
4
|
15 5
0 0 2 -2 2 -2 3 -3 -3 4 5 -4 -4 4 5
|
18119684
|