CF1696H.Maximum Product?

You are given a positive integer $k$. For a multiset of integers $S$, define $f(S)$ as the following.

• If the number of elements in $S$ is less than $k$, $f(S)=0$.
• Otherwise, define $f(S)$ as the maximum product you can get by choosing exactly $k$ integers from $S$.

More formally, let $|S|$ denote the number of elements in $S$. Then,

• If $|S| \lt k$, $f(S)=0$.
• Otherwise, $f(S)=\max\limits_{T\subseteq S,|T|=k}\left(\prod\limits_{i\in T}i\right)$.

You are given a multiset of integers, $A$. Compute $\sum\limits_{B\subseteq A} f(B)$ modulo $10^9+7$.

Note that in this problem, we distinguish the elements by indices instead of values. That is, a multiset consisting of $n$ elements always has $2^n$ distinct subsets regardless of whether some of its elements are equal.

给你一个正整数 $k$。对于一个整数多重集 $S$，定义函数 $f(S)$ 如下：

• 若 $S$ 中元素个数小于 $k$，则 $f(S) = 0$；
• 否则，$f(S)$ 定义为从 $S$ 中恰好选出 $k$ 个整数所能得到的最大乘积。

更形式化地，令 $|S|$ 表示 $S$ 中元素的个数，则：

• 若 $|S| \lt 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$ 个互不相同的子集，无论其中是否存在相等的元素。

The first line of input contains two integers $n$ and $k$, where $n$ is the number of elements in $A$ ($1\le k\le n\le 600$).

The second line of input contains $n$ integers $a_1,a_2,\dots,a_n$, describing the elements in $A$ ($-10^9\le a_i\le 10^9$).

输入的第一行包含两个整数 $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$）。

Output $\sum\limits_{B\subseteq A} f(B)$ modulo $10^9+7$.

输出 $\sum\limits_{B\subseteq A} f(B)$ 对 $10^9+7$ 取模的结果。

Consider the first sample. From the definitions we know that

• $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$

So we should print $(0+0+0+0-2-4+8+8)\bmod (10^9+7)=10$.

In the second example, note that although the multiset consists of three same values, it still has $8$ distinct subsets: $\varnothing,{1},{1},{1},{1,1},{1,1},{1,1},{1,1,1}$.

考虑第一个样例。根据定义，我们知道：

• $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}$。