Problem 3. OohMoo Milk

USACO 2025 US Open Contest, Gold

Farmer John 正在试着售出他举世闻名的奥哞牛奶以获取利润。他有 $N$（$1 \leq N \leq 10^5$）个瓶子正在尝试灌装。每个瓶子初始时含有 $m_i$（$0 \leq m_i \leq 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 \leq D \leq 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$ 取模。

输入样例：

5 4
4 2
4 10 8 10 10

输出样例：

546

第一天，Farmer John 可以向第二，第三，第四和第五个瓶子添加牛奶。然后，Farmer Nhoj 可以从第二和第四个瓶子中移除牛奶。

因此，每个瓶子中的新牛奶量为

$$[4, 10, 8, 10, 10] \to [4, 11, 9, 11, 11] \to [4, 10, 9, 10, 11]$$

经过四天，每个瓶子中的牛奶量可能为

$$[4, 10, 8, 10, 10] \to [4, 10, 9, 10, 11] \to [4, 10, 10, 11, 11] \to [4, 11, 11, 11, 11] \to [4, 11, 11, 12, 12]$$

在这种情况下，Farmer John 所能赚取的总哞尼数为 $4^2+11^2+11^2+12^2+12^2 = 546$。可以证明这就是 $P$ 的值。

输入样例：

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

输出样例：

777

输入样例：

5 1000000000
3 1
0 1 2 3 4

输出样例：

10

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

测试点性质： 测试点 4-6：$N,D\le 1000$。测试点 7-10：$D\le 10^6$。测试点 11-20：没有额外限制。

供题：Suhas Nagar