문제
Farmer John은 세계적으로 유명한 OohMoo Milk를 만들어 이윤을 창출하려고 합니다. 현재 그는 N개의 병(1 ≤ N ≤ 10^5)을 채우려 하고 있으며, 각 병은 처음에 m_i (0 ≤ m_i ≤ 10^9) 단위의 우유를 담고 있습니다. 매일, Farmer John은 A (1 ≤ A ≤ N)개의 병을 선택하여 각각의 병에 우유 1 단위를 채웁니다.
하지만 경쟁자 Farmer Nhoj는 Farmer John의 생산 과정을 알아내어 사업을 방해할 계획을 세웠습니다. 매일, Farmer John이 A개의 병에 우유를 채운 후, Farmer Nhoj는 몰래 B (0 ≤ B < A)개의 서로 다른 빈 병이 아닌 병에서 우유 1 단위를 훔쳐 갑니다. Farmer Nhoj는 A보다 작은 B를 선택하여, Farmer John이 자신을 발견하지 못하게 하려고 합니다.
D일 (1 ≤ D ≤ 10^9) 후에 Farmer John은 OohMoo Milk를 판매합니다. 만약 한 병에 M 단위의 우유가 담겨 있다면, 그 병은 M^2 moonies의 가격에 판매됩니다.
P를, Farmer John이 어떻게 행동하든 적어도 P의 이익을 보장받을 수 있고, Farmer Nhoj가 어떻게 행동하든 Farmer John이 P 이상의 이익을 만들지 못하도록 보장할 수 있는 유일한 이익값이라고 하겠습니다. 문제는 P의 값을 10^9+7로 나눈 나머지를 구하는 것입니다.
입력
첫 번째 줄에 병의 개수 N와 일수 D가 주어집니다.
두 번째 줄에는 A와 B가 주어집니다.
세 번째 줄에는 N개의 정수 m_i (각 병에 들어있는 초기 우유의 양)이 공백으로 구분되어 주어집니다.
출력
출력은 표준 출력에 한 줄로 나타내며, P의 값을 10^9+7로 나눈 나머지를 출력합니다.
예제 #1
5 4
4 2
4 10 8 10 10
546
첫째 날, Farmer John은 두 번째, 세 번째, 네 번째, 다섯 번째 병에 우유를 추가할 수 있습니다. 그 후, Farmer Nhoj는 두 번째와 네 번째 병에서 우유를 한 단위씩 훔칩니다.
따라서 각 병의 우유 양은 다음과 같이 바뀝니다:
[4, 10, 8, 10, 10] -> [4, 11, 9, 11, 11] -> [4, 10, 9, 10, 11].
4일이 지난 후, 가능한 우유의 양은 다음과 같을 수 있습니다:
[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].
이때, 판매 금액은 각 병의 우유 양의 제곱의 합으로, 4^2 + 11^2 + 11^2 + 12^2 + 12^2 = 546 moonies입니다. 이 값이 P임이 증명됩니다.
예제 #2
10 5
5 1
1 2 3 4 5 6 7 8 9 10
777
예제 #3
5 1000000000
3 1
0 1 2 3 4
10
로그인해야 코드를 작성할 수 있어요.