题目描述

在遥远的未来，人类建立了一个由 $N$ 个空间站组成的线性网络。为了维持空间站的运行，需要从第 $1$ 号空间站向第 $N$ 号空间站传输能量。

每个空间站 $i$ ($1 \le i \le N$) 拥有一定的基础能量值 $A_i$。当能量从空间站 $i$ 传输到空间站 $j$ ($i < j$) 时，除了需要支付固定的传输成本 $C_{i,j}$ 外，还需要消耗一定的能量。

具体规则如下：

1. 定义前缀和 $S_i = \sum_{k=1}^{i} A_k$。
2. 从空间站 $i$ 传输到空间站 $j$ ($i < j$) 的能量消耗为 $(S_j - S_i)^2$。
3. 固定传输成本 $C_{i,j}$ 由公式 $K \cdot (j - i)$ 给出，其中 $K$ 是一个给定的常数。

你需要将网络划分为若干个连续的区间，使得能量从第 $1$ 号空间站出发，经过一系列跳跃最终到达第 $N$ 号空间站的总消耗最小。 设 $f[i]$ 表示能量到达第 $i$ 号空间站时的最小总消耗。 显然 $f[1] = 0$。 对于 $j > 1$，状态转移方程为：

$$f[j] = \min_{1 \le i < j} \left( f[i] + (S_j - S_i)^2 + K \cdot (j - i) \right)$$

请计算 $f[N]$ 的值。由于答案可能很大，请对 $10^9 + 7$ 取模后输出。 注意：$S_N$ 可达 $10^{14}$，$(S_j - S_i)^2$ 可达 $10^{28}$，比较大小时必须使用未取模的精确值（如 __int128），只在最后输出时取模。

输入格式

第一行包含两个整数 $N$ 和 $K$，分别表示空间站的数量和固定传输成本系数。 第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$，表示每个空间站的能量值。

数据范围与提示

对于 $100\%$ 的数据：

• $2 \le N \le 10^5$
• $1 \le K \le 10^9$
• $1 \le A_i \le 10^9$

提示：

1. 观察状态转移方程，发现其具有斜率优化的特征。
2. 可以将方程展开为关于 $S_j$ 的线性函数形式，利用单调队列维护凸包。
3. 注意 $A_i$ 为正数，因此前缀和 $S_i$ 是严格单调递增的，这保证了决策点的单调性。

样例

4 2
1 2 3 4

35

样例解释

$S = [1, 3, 6, 10]$。最优方案是逐站传输 $1 \to 2 \to 3 \to 4$：

• $1 \to 2$：$(3-1)^2 + 2 \times 1 = 6$
• $2 \to 3$：$(6-3)^2 + 2 \times 1 = 11$
• $3 \to 4$：$(10-6)^2 + 2 \times 1 = 18$

总消耗 $6 + 11 + 18 = 35$。其他方案均不更优，例如 $1 \to 3 \to 4$ 为 $29 + 18 = 47$，$1 \to 4$ 为 $87$。