贪心外套计数

[AGC049E] Increment Decrement

一个序列 \(A\) 有一个权值：

• 序列 \(a\) 元素都等于 \(0\)，能进行若干次操作
  • 单点加 \(1\) 或 \(-1\)，花费为 \(1\)。
  • 区间加 \(1\) 或 \(-1\)，花费为 \(C\)。
• \(a\) 变成 \(A\) 的最小花费，即为 \(A\) 的权值。
  给 \(n\) 个长 \(k\) 的序列 \(B_1,B_2,B_3,\cdots,B_n\)。序列 \(A\) 的所有 \(A_i\) 在 \(B_i\) 中选一个，共 \(k^n\) 种，求 \(k^n\) 种序列 \(A\) 的权值之和，对 \(10^9 + 7\) 取模。