Given an array of integers {xi}. Each time you can apply one of the following operations to the array: 1. Choose an integer x from the array, replace it with x+1. 2. Add a new integer 1 to the array.
Define p as the product of all integers in the set. i.e. p=x1*x2*x3*... What's the maximum possible value of p after exactly M operations?
输入解释
First line is a integer T (T ≤ 100), the number of test cases. The first line of each test case contains two integers N and M, the number of integers in the initial set, and the number of operations. The second line is N integers xi initially in the set. 1 ≤ N ≤ 100000 0 ≤ M ≤ 10^18 -10000 ≤ xi ≤ 10000
输出解释
For each case, you should output “Case k: ” first, where k indicates the case number and counts from one. Then the maximum product mod 1000000007.