题目描述

给出 $n,k$ 和 $n$ 个整数 $a_1\sim a_n$，对 $\{a_1,a_2,\dots,a_n\}$ 的每一个子集解决下面的问题，然后把答案求和，对 $10^9+7$ 取模：

从这个集合中选出恰好 $k$ 个数，最大乘积是多少？（如果集合内数的个数小于 $k$，认为最大乘积是 $\color{red}0$）

注意，要求的是最大值取模后的结果，不是取模后的最大值。

输入格式

第一行两个正整数 $n,k$。

接下来一行 $n$ 个整数 $a_1\sim a_n$。

输出格式

一行一个整数，为答案对 $10^9+7$ 取模的值。

样例

样例输入 1

10 1
-2 -9 -7 -4 -5 4 -3 2 -8 5

样例输出 1

3459

样例输入 2

7 3
1 -2 3 -4 5 -6 7

样例输出 2

5828

样例输入 3

10 5
0 -2 0 -4 5 -6 7 8 -4 6

样例输出 3

1114688

样例输入 4

15 5
0 0 2 -2 2 -2 3 -3 -3 4 5 -4 -4 4 5

样例输出 4

18119684

数据范围

本题捆绑测试。

对于所有数据，$1\le k\le n\le 600$，$-10^9\le a_i\le 10^9$。详细数据范围如下表：