Dirty Sum

0

0 votes
Hard
Problem

You are given an array of N integers, where value of i​​​​​​ith​​​ 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

1N105

1K200

0A[i]109

Sample Input
3 2
1 1 1



Sample Output
10


Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?