Alexa has an array Arr of size N. She can perform at-most K operations on the array. In each operation she will perform the following tasks:

• Choose and element Arr[i] from array and add one to this element. This means that after this operation Arr[i] = Arr[i] + 1

If she performs operations optimally, find Maximum possible value of multiplication of all the array elements after at-most K operations. return answer in modulo 10⁹ + 7

Example:

N - 1
K - 1
A - 1
OUTPUT : 2

We have only one element and we need to perform 1 operation hence answer is 2

Example:

2
5
0 4
OUTPUT : 20

Perform all 5 operations on the first element, array will become [5, 4]
output is 20

Example:

2
5
0 2
OUTPUT : 12

perform 4 operations on index 0
perform 1 opeartion on index 1
array will become [4, 3]
answer is 12