OohMoo Milk Equilibrium Profit

Farmer John produces his famous OohMoo milk for profit. He has (N) bottles, with the (i)-th bottle initially containing (m_i) units of milk. Every day, John selects (A) bottles and adds 1 unit of milk to each of them. Unfortunately, after John’s additions, his rival, Farmer Nhoj, sabotages the process by stealing 1 unit of milk from each of (B) different non-empty bottles (with (0 \le B < A)). This process is repeated for (D) days.

When a bottle ends up with (M) units of milk, it is sold for (M^2) moonies. Define (P) as the unique profit value such that, no matter how Nhoj acts, John is guaranteed to earn at least (P) moonies, while regardless of John’s actions, Nhoj can ensure that John's profit does not exceed (P).

Your task is to compute (P \bmod (10^9+7)).

Insight: Since John adds milk in total (D\cdot A) units and Nhoj removes (D\cdot B) units overall, John can guarantee a net addition of milk in exactly (A-B) bottles if he concentrates his additions optimally. Specifically, assume John selects the following strategy: each day, he chooses the same set of (A) bottles where he allocates his additions such that the (A-B) bottles with the highest initial values receive no sabotage (and hence gain (D) units), while the other (B) bottles receive milk only to be fully counteracted by Nhoj’s sabotage. The final milk amount in a bottle that is protected becomes (m_i + D), and its contribution to the profit is ((m_i + D)^2). For an unsupplemented bottle, the profit remains (m_i^2).

Thus, if we denote the initial profit (from all bottles) as (\sum_{i=1}^{N} m_i^2) and let (S) be the set of the ((A-B)) bottles with the largest (m_i) values, then the additional profit obtained by protecting these bottles is (\sum_{i \in S} \Bigl[(m_i + D)^2 - m_i^2\Bigr] = \sum_{i \in S} (2m_iD + D^2)). Hence,

[ P = \sum_{i=1}^{N} m_i^2 + \left(\sum_{i\in S} 2m_iD + (A-B)\cdot D^2\right). ]

Compute this value modulo (10^9+7).

inputFormat

The first line contains four integers \(N\), \(A\), \(B\), and \(D\) (with \(1 \le N \le 10^5\), \(1 \le A \le N\), \(0 \le B < A\), \(1 \le D \le 10^9\)).

The second line contains \(N\) integers \(m_1, m_2, \ldots, m_N\) (with \(0 \le m_i \le 10^9\)), where \(m_i\) denotes the initial amount of milk in the \(i\)-th bottle.

outputFormat

Output a single integer: \(P \bmod (10^9+7)\).

sample

3 2 1 1
1 2 3

21