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|

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

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\} $ .