A15258 | 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|<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.

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$ ).

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