OohMoo Milk

문제

Farmer John is trying to make his world's famous OohMoo Milk to sell for a profit. He has $NN$ $(1\le N\le {10}^5)(1\; \backslash leq\; N\; \backslash leq\; 10^5)$ bottles that he is trying to fill. Each bottle initially contains some amount of milk $m_{i}m\_i$ $(0\le m_i\le {10}^9)(0\; \backslash leq\; m\_i\; \backslash leq\; 10^9)$. Every day, he takes $AA$ $(1\le A\le N)(1\; \backslash le\; A\; \backslash le\; 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 $AA$ bottles, Farmer Nhoj will sneakily steal one unit of milk from each of $BB$ different nonempty bottles. To remain sneaky, Farmer Nhoj chooses $BB$ so that it is strictly less than $AA$, so that it is less likely for Farmer John to discover him.

After $DD$ ($1\le D\le {10}^{9}1\; \backslash leq\; D\; \backslash leq\; 10^9$) days, Farmer John will sell his OohMoo Milk. If a bottle has $MM$ units of milk, it will sell for $M^{2}M^2$ moonies.

Let $PP$ be the unique profit such that FJ can guarantee that he makes at least $PP$ profit regardless of how FN behaves, and FN can guarantee that FJ makes at most $PP$ profit regardless of how FJ behaves. Output the value of $PP$ modulo ${10}^9+710^9+7$.

입력

The first line of the input contains $NN$ and $DD$, where $NN$ is the number of bottles and $DD$ is the number of days that take place.

The second line of the input contains $AA$ and $BB$ representing the number of units of milk that Farmer John fills and Farmer Nhoj steals respectively.

The third line of the input contains $NN$ space-separated integers $m_{i}m\_i$ representing the initial amount of milk in each bottle.

출력

Output the value of $PP$ modulo ${10}^9+710^9+7$.

5 4
4 2
4 10 8 10 10

546

10 5
5 1
1 2 3 4 5 6 7 8 9 10

777

5 1000000000
3 1
0 1 2 3 4

10