У Фермера Джона есть \(N\) \((1 \leq N \leq 10^5)\) бутылок, которые он хочет
наполнить молоком. Каждая бутылка изначально содержит некоторое количество
молока \(m_i\) \((0 \leq m_i \leq 10^9)\). Каждый день он берёт \(A\) \((1 \le A \le N)\)
бутылок и наполняет одной единицей молока.
К несчастью, Фермер Нхой, соперник ФД по бизнесу, знает об этом процессе ФД и
намерен навредить. Каждый день после того, как ФД заполнит свои \(A\) бутылок,
ФН незаметно крадёт одну единицу молока из \(B\) \((0 \le B < A)\) различных
непустых бутылок. Чтобы оставаться незамеченным, ФН выбирает \(B\) так, чтобы
оно было строго меньше чем \(A\).
После \(D\) (\(1 \leq D \leq 10^9\)) дней ФД продаёт своё молоко. Если в бутылке
\(M\) единиц молока, он продаёт эту бутылку за \(M^2\) денежных единиц.
Пусть \(P\) - уникальная прибыль, такая, что FJ может гарантировать, что он получит не менее
\(P\) прибыли независимо от того, как ведет себя FN, а FN может гарантировать, что FJ получит не более
\(P\) прибыли независимо от того, как ведет себя FJ. Выведите значение \(P\) по модулю
\(10^9+7\).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(N\) и
\(D\), где
\(N\) это количество бутылок, а
\(D\) - количество
дней.
Вторая строка содержит \(A\) и \(B\) количество единиц молока, которое ФД добавляет,
а ФН вычитает соответственно.
Третья строка содержит \(N\) разделённых пробелами целых чисел \(m_i\),
представляющих изначальное количество молока в бутылках.
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите значение \(P\) по модулю \(10^9+7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 4
4 2
4 10 8 10 10
|
546
|