06777. USACO·牛奶博弈 未做

Farmer John 正在试着售出他举世闻名的奥哞牛奶以获取利润。他有 $N$（$1\le N\le 10^5$）个瓶子正在尝试灌装。每个瓶子初始时含有 $m_i$（$0\le m_i\le 10^9$）单位的牛奶。每天，他会选择 $A$（$1\le A\le N$）个瓶子并为每个瓶子添加一单位的牛奶。

不幸的是，Farmer Nhoj，Farmer John 在奥哞牛奶业务上的的竞争对手，得知了 Farmer John 的生产过程，计划削弱他的业务。每天，在 Farmer John 灌装他的 $A$ 个瓶子后，Farmer Nhoj 会偷偷从 $B$（$0\le B<A$）个不同且非空的瓶子中各偷走一单位的牛奶。为了保持隐秘，Farmer Nhoj 选择 $B$ 使其严格小于 $A$，这样 Farmer John 就不太可能发现他。

$D$（$1\le D\le 10^9$）天后，Farmer John 将售出他的奥哞牛奶。如果一个瓶子内有 $M$ 单位的牛奶，它将以 $M^2$ 哞尼的价格出售。

令 $P$ 为唯一的利润值，使得 FJ 可以保证无论 FN 如何行为，他至少获得 $P$ 的利润，而 FN 可以保证无论 FJ 如何行为，FJ 至多获得 $P$ 的利润。输出 $P$ 的值，答案对 $10^9+7$ 取模。

输入的第一行包含 $N$ 和 $D$，其中 $N$ 是瓶子的数量，$D$ 是经过的天数。

第二行包含 $A$ 和 $B$，分别表示 Farmer John 添加的以及 Farmer Nhoj 偷走的牛奶单位数。

第三行包含 $N$ 个空格分隔的整数 $m_i$，表示每个瓶子的初始牛奶量。

输出一行，包含 $P$ 的值，答案对 $10^9+7$ 取模。

【样例解释】

确保输出 $P$ 时对 $10^9+7$ 取模。

• 测试点 7-10：$D\le 10^6$。

• 测试点 11-20：没有额外限制。

【数据规模与约定】

• 测试点 4-6：$N,D\le 1000$。

• 测试点 7-10：$D\le 10^6$。

• 测试点 11-20：没有额外限制。

供题：Suhas Nagar