class Solution {
    long ans = Long.MIN_VALUE;

    public int maximumProduct(int[] nums, int k) {
        maximumProductSub(nums, k, 0, 1);
        return (int) ans;
    }

    public void maximumProductSub(int[] nums, int k, int index, long tempAns) {
        if (index == nums.length) {
            if (tempAns > ans) {
                ans = tempAns;
            }
            return;
        }
        for (int j = 0; j <= k; j++) {
            maximumProductSub(nums, k - j, index + 1, tempAns * (nums[index] + j) % 1000000007);
        }
    }
}