존은 이익을 내기 위해 세계적으로 유명한 OohMoo Milk를 만들어 판매하려고 한다. 존은 우유를 채우려는 병을 \(N\)개 가지고 있다. \((1 \le N \le 100,000)\) 처음에 \(i\)번째 병에는 \(m_i\)만큼의 우유가 들어 있다. \((0 \le m_i \le 1,000,000,000)\) 매일 존은 \(A\)개의 병을 골라 각 병에 우유를 한 단위씩 채운다. \((1 \le A \le N)\)

불행히도 OohMoo Milk 사업에서 존의 경쟁자인 노존은 존의 생산 과정을 알고 있으며, 그의 사업을 방해할 계획을 세웠다. 매일 존이 \(A\)개의 병에 우유를 채운 뒤, 노존은 비어 있지 않은 서로 다른 \(B\)개의 병에서 우유를 한 단위씩 몰래 훔친다. \((0 \le B < A)\) 노존은 존에게 들킬 가능성을 줄이기 위해 \(B\)가 \(A\)보다 엄격히 작도록 정했다.

\(D\)일이 지난 뒤 존은 OohMoo Milk를 판매한다. \((1 \le D \le 1,000,000,000)\) 어떤 병에 우유가 \(M\)만큼 들어 있다면 그 병은 \(M^2\) 무니에 팔린다.

존이 어떻게 행동하더라도 노존이 존의 이익을 최대 \(P\)로 만들 수 있고, 노존이 어떻게 행동하더라도 존이 최소 \(P\)의 이익을 얻을 수 있게 하는 유일한 이익 \(P\)가 존재한다고 하자. \(P\)를 \(1,000,000,007\)로 나눈 나머지를 출력하여라.

입력

첫째 줄에 병의 수 \(N\)과 진행되는 날의 수 \(D\)가 주어진다.

둘째 줄에 존이 채우는 우유의 단위 수 \(A\)와 노존이 훔치는 우유의 단위 수 \(B\)가 주어진다.

셋째 줄에 각 병에 처음 들어 있는 우유의 양을 나타내는 \(N\)개의 정수 \(m_i\)가 공백으로 구분되어 주어진다.

출력

\(P\)를 \(1,000,000,007\)로 나눈 나머지를 출력한다.

예제 입력 1

5 4
4 2
4 10 8 10 10

예제 출력 1

546

예제 설명 1

첫째 날, 존은 두 번째, 세 번째, 네 번째, 다섯 번째 병에 우유를 추가할 수 있다. 그다음 노존은 두 번째 병과 네 번째 병에서 우유를 제거할 수 있다.

따라서 각 병에 들어 있는 우유의 양은 다음과 같이 변한다.

\([4,10,8,10,10] \rightarrow [4,11,9,11,11] \rightarrow [4,10,9,10,11]\)

4일이 지난 뒤 각 병에 들어 있는 우유의 양은 다음과 같을 수 있다.

\([4,10,8,10,10] \rightarrow [4,10,9,10,11] \rightarrow [4,10,10,11,11] \rightarrow [4,11,11,11,11] \rightarrow [4,11,11,12,12]\)

이 상황에서 존이 얻는 무니의 총량은 \(4^2+11^2+11^2+12^2+12^2=546\)이다. 이 값이 \(P\)임을 보일 수 있다.

예제 입력 2

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

예제 출력 2

777

예제 입력 3

5 1000000000
3 1
0 1 2 3 4

예제 출력 3

10

예제 설명 3

\(P\)를 \(1,000,000,007\)로 나눈 나머지를 출력해야 한다.

출처

USACO 2025 US Open Contest, Gold, Problem 3. OohMoo Milk