Farmer John is trying to make his world's famous OohMoo Milk to sell for a profit. He has N (1≤N≤105) bottles that he is trying to fill. Each bottle initially contains some amount of milk mi (0≤mi≤109). Every day, he takes A (1≤A≤N)
bottles and fills each bottle with one unit of milk.
Unfortunately, Farmer Nhoj, Farmer John's competitor in the business of OohMoo Milk, knows about Farmer John's production processes and has a plan 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 (0≤B<A) different nonempty bottles. To remain sneaky, Farmer Nhoj chooses B so that it is strictly less than A, so that it is less likely for Farmer John to discover him.
After D(1≤D≤109) days, Farmer John will sell his OohMoo Milk. If a bottle has M
units of milk, it will sell for M2 moonies.
Let P be the unique profit such that FJ can guarantee that he makes at least P profit regardless of how FN behaves, and FN can guarantee that FJ makes at most P profit regardless of how FJ behaves. Output the value of P modulo 109+7.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line of the input contains N and D, where N is the number of bottles and D is the number of days that take place.
The second line of the input contains A and B representing the number of units of milk that Farmer John fills and Farmer Nhoj steals respectively.
The third line of the input contains N space-separated integers mi representing the initial amount of milk in each bottle.
OUTPUT FORMAT (print output to the terminal / stdout):
Output the value of P modulo 109+7.
SAMPLE INPUT:
5 4
4 2
4 10 8 10 10
SAMPLE OUTPUT:
546
On the first day, Farmer John could add milk to the second, third, fourth, and fifth bottles. Then, Farmer Nhoj could remove milk from the second and fourth bottles.
Thus, the new amount of milk in each bottle is
[4,10,8,10,10]→[4,11,9,11,11]→[4,10,9,10,11].
After four days, the amount of milk in each bottle could be
[4,10,8,10,10]→[4,10,9,10,11]→[4,10,10,11,11]→[4,11,11,11,11]→[4,11,11,12,12].
The total amount of moonies Farmer John would make in this situation is 42+112+112+122+122=546. It can be shown that this is the value of P.
SAMPLE INPUT:
10 5
5 1
1 2 3 4 5 6 7 8 9 10
SAMPLE OUTPUT:
777
SAMPLE INPUT:
5 1000000000
3 1
0 1 2 3 4
SAMPLE OUTPUT:
10
Make sure you output P modulo 109+7.
SCORING:
Inputs 4-6: N,D≤1000.
Inputs 7-10: D≤106.
Inputs 11-20: No additional constraints.
Problem credits: Suhas Nagar
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
