哎，当时比赛的时候各种胡思乱想，竟然把这道题给A了。
这题的题意就是给一序列的数，有两种操作，一种是把序列中某个数的值加1，要么在序列中增添一个数为1，然后给出操作数，最后要求这些数的乘积最大，求出这个乘积。
做这个题要考虑的细节很多，首先要把负数的个数求出，如果为奇数，那么要把最大的那个负数尽量加到0，就相当于转化为偶数的情况了，然后负数就不用在管了，这时候，序列中如果有0的话，很显然他们相乘就是0，所以尽量把所有的0要变成1，之后，如果操作数还有剩余，就要尽量把所有的1变成2了，因为1在序列中是没有任何用处的，增加到2就是翻一番，用1个操作数达到这种效果是最划算的，之后如果操作数还有剩余，再把所有的2变成3，因为两个操作可以在序列中新增添一个2，也可以将两个2变为两个3，这样分析一下，明显是把两个2变为两个3更为划算，一个操作的时候显然也是把2变为3更划算，之后，如果操作数还有剩余，那么，当操作数为1的时候，很显然是加到最小的那个正数上比较划算，但是操作数大于1的时候，我们可以假设序列中有很多个3，那么3+1所获得的增幅是4/3，那么我们可以比较在序列中新增一个数和把这么些个3加1所造成的增幅，可以发现，2,3,4,5,6的时候在序列中新增一个数所造成的增幅是大于在3的基础上加1的，而且，所有数是可以被2和3以加法形式组成的，例如6=3+3，很明显，6拆成3和3所造成的增幅要比自己靠谱，所以我们尽量把操作数拆分为2或者3，但是是谁更优先呢？ 我们可以发先，如果3*a=2*b,那么3^a一定大于2^b，所以，最优先的应该是3，所以，我们应该尽量往序列中加3，然后再加2，使3*a+2*b=操作数。代码如下
/*
ID: sdj22251
PROG: lamps
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAX 200000000
#define LOCAL
using namespace std;
__int64 a[100005];
__int64 f(__int64 a,__int64 n,__int64 m)
{__int64 x;if(n == 0)return 1 % m;else if(n % 2 == 0){x=f(a, n / 2, m);return x % m * x % m;}else{x=f(a, (n - 1) / 2, m);return x % m * x % m * a % m;}
}
int main()
{int n, m, t, cas, i, Negative, loc, Negativemax, Positiveminus, loc2;__int64 two ,three;__int64 mod = (__int64)1000000007;while(scanf("%d", &t) != EOF){cas = 0;while(t--){loc = 0;Negative = 0;two = 0;three = 0;Positiveminus = MAX;Negativemax = -MAX;scanf("%d%d", &n, &m);for(i = 0; i < n; i++){scanf("%I64d", &a[i]);if(a[i] < 0){Negative++;if(a[i] > Negativemax){Negativemax = a[i];loc = i;}}}if(Negative % 2){if(a[loc] + m >= 0){m -= (0 - a[loc]);a[loc] = 0;}else{a[loc] += m;m = 0;}}if(m > 0){for(i = 0; i < n; i++){if(a[i] == 0){if(m > 0){a[i]++;m--;}else break;}}}if(m > 0){for(i = 0; i < n; i++){if(a[i] == 1){if(m > 0){a[i]++;m--;}else break;}}}if(m > 0){for(i = 0; i < n; i++){if(a[i] == 2){if(m > 0){a[i]++;m--;}else break;}}}if(m > 0){loc2 = 0;for(i = 0; i < n; i++){if(a[i] < Positiveminus){Positiveminus = a[i];loc2 = i;}}if(m % 3 == 0){three += m / 3;}else if(m % 3 == 1){if(m == 1){a[loc2]++;m = 0;}else{three += m / 3 - 1;two += 2;}}else if(m % 3 == 2){three += m / 3;two++;}}__int64 tmp = 1;for(i = 0; i < n; i++){tmp = tmp * a[i] % mod;}__int64 threenum = f((__int64)3, three, mod);__int64 twonum = f((__int64)2, two, mod);tmp = tmp * threenum % mod * twonum % mod;printf("Case %d: %I64d\n", ++cas, tmp % mod);}}return 0;
}