You are given an array of N integers, where value of iith integer of the array is A[i]. You have to divide the whole array into K disjoint subarrays such that each element of the array belongs to exactly one of the subarrays. As there are numerous ways to partition the array in the above manner, for each of them, we define a Dirty Sum which is the summation of the Dirty Values of all the K disjoint subarrays. The Dirty Value of a subarray is defined as the square of the sum of all elements of that subarray.
You have to return the summation of the Dirty Sum of all the possible partitions of the array modulo 109 + 7.
Input Format
The first line of input contains 2 space separated integers N and K.
The second line of input contains N space separated integers numbered from 1 to N where ith integer stands for A[i].
Output Format
Print a single intger which is equal to the summation of the Dirty Sum of all the possible partitions of the array modulo 109 + 7..
Constraints