[USACO25OPEN] OohMoo Milk G

题目描述

农夫约翰正在生产他世界闻名的 OohMoo 牛奶以获取利润。他有 $N$ 个（$1 \leq N \leq 10^5$）瓶子需要装牛奶，每个瓶子初始含有 $m_i$（$0 \leq m_i \leq 10^9$）单位的牛奶。每天，他会选择 $A$ 个（$1 \leq A \leq N$）瓶子，每个被选中的瓶子增加 $1$ 单位牛奶。

不幸的是，他的竞争对手农夫 Nhoj 知道这个生产过程并计划破坏。每天在农夫约翰添加牛奶后，农夫 Nhoj 会偷偷从 $B$ 个（$0 \leq B < A$）不同的非空瓶子中各偷走 $1$ 单位牛奶。为了不被发现，农夫 Nhoj 确保 $B$ 严格小于 $A$。

经过 $D$ 天（$1 \leq D \leq 10^9$）后，农夫约翰将出售他的牛奶。如果一个瓶子含有 $M$ 单位牛奶，它将卖出 $M^2$ moonies 的价钱。

设 $P$ 为唯一确定的利润值，使得无论农夫 Nhoj 如何操作，农夫约翰都能保证至少获得 $P$ 利润；同时无论农夫约翰如何操作，农夫 Nhoj 都能确保农夫约翰最多获得 $P$ 利润。请输出 $P$ 对 $10^9+7$ 取模的结果。

输入格式

第一行包含 $N$ 和 $D$，分别表示瓶子数量和天数。

第二行包含 $A$ 和 $B$，表示农夫约翰每天添加的牛奶瓶数和农夫 Nhoj 每天偷取的瓶数。

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

输出格式

输出 $P$ 对 $10^9+7$ 取模的结果。

输入输出样例 #1

输入 #1

5 4
4 2
4 10 8 10 10

输出 #1

546

输入输出样例 #2

输入 #2

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

输出 #2

777

输入输出样例 #3

输入 #3

5 1000000000
3 1
0 1 2 3 4

输出 #3

10

说明/提示

样例一解释：经过 $4$ 天后，可能的牛奶量为 $[4,11,11,12,12]$，总利润为 $4^2+11^2+11^2+12^2+12^2=546$。

• 测试点 $4\sim6$：$N,D \leq 1000$。
• 测试点 $7\sim10$：$D \leq 10^6$。
• 测试点 $11\sim20$：无额外限制。