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로 나눈 나머지를 구하는 것입니다.

#8420 upload - done - how_to_reg -

OohMoo Milk timer 1s memory 1024MB

#8420

OohMoo Milk 1s 1024MB