Problems
Farmer John is trying to make his world's famous OohMoo Milk to sell for a profit. He has N bottles (1 ≤ N ≤ 10^5) that he is trying to fill, and each bottle initially contains some amount of milk m_i (0 ≤ m_i ≤ 10^9). Every day, he takes A bottles (1 ≤ A ≤ N) and fills each bottle with one unit of milk.
Unfortunately, Farmer Nhoj, Farmer John's competitor in the business of OohMoo Milk, is aware of Farmer John's production processes and plans to curtail his business. Every day, after Farmer John fills his A bottles, Farmer Nhoj will sneakily steal one unit of milk from each of B different nonempty bottles (0 ≤ B < A). To remain sneaky, Farmer Nhoj chooses B so that it is strictly less than A.
After D days (1 ≤ D ≤ 10^9), Farmer John will sell his OohMoo Milk. If a bottle has M units of milk, it will sell for M^2 moonies.
Let P be the unique profit such that Farmer John can guarantee he makes at least P profit regardless of how he behaves, and Farmer Nhoj can guarantee that Farmer John makes at most P profit regardless of how Farmer John behaves. Output the value of P modulo 10^9+7.
Input
The first line contains two integers N and D, where N is the number of bottles and D is the number of days.
The second line contains two integers A and B representing the number of bottles that Farmer John fills and the number of bottles from which Farmer Nhoj steals one unit of milk, respectively.
The third line contains N space-separated integers m_i, representing the initial amount of milk in each bottle.
Output
Output a single line containing the value of P modulo 10^9+7.
Example #1
5 4
4 2
4 10 8 10 10
546
5 1000000000
3 1
0 1 2 3 4
Example #2
10 5
5 1
1 2 3 4 5 6 7 8 9 10
777
Example #3
5 1000000000
3 1
0 1 2 3 4
10
You must sign in to write code.