You are given an array $A$ of $N$ elements. Now, you need to perform exactly $K$ cuts in the array such that the array is divided into $K + 1$ non-empty subarrays. Now, after the array is divided into different parts you need to take the product of elements in each of the part and then take the sum of all these products. Since, there are lots of ways to partition the array into $K + 1$ subarrays so you need to print this sum of products over all possible cuts. Print the value of this sum modulo $720720$.

Note: Please checkout the sample explanation carefully for better understanding of the problem.

Input Format
The first line contains an integer $N$ as input that denotes the total number of elements in the array.
The next line contains $N$ space-separated integers that denote the elements of the array.
The next line of the input contains an integer $K$ that denotes the total number of cuts that need to be made on the array $A$.

Output Format
In the output, you need to print the sum of products of all the subarrays across all the possible different cuts modulo $720720$.

Constraints
$2 \le N \le 100$
$1 \le K \le N - 1$
$1 \le A[i] \le 10^9$