P17317 [KismetOI 2026 I] 作弊

cobeder 开始举办 rated 比赛了。小 A 参加了 $n$ 场比赛，其中第 $i$ 场比赛的 perf 值为 $p_i$（$|p_i| \le V$）。cobeder 系统有个常数值 $k$ 和一个数组 $g_{0 \sim kV}$，对于小 A 的 rating 值，可以用以下方式计算： - 若 $n \le k$。则 rating 值等于 $g_{\max\limits_{i=0}^{n}(\sum\limits_{j=1}^{i}p_j)}$。 - 若 $n > k$。记 $\text{maxp} = \max\limits_{i=0}^{k}(\sum\limits_{j=1}^{i}p_j)$。则 rating 值等于 $g_{\text{maxp}} \times (\sum\limits_{i=1}^{n}p_i)$。 **特别的，当 $i=0$ 时令 $\sum\limits_{j=1}^{i}p_j=0$。** 小 A 入侵了 cobeder 的系统，他想要借此机会修改他的 rating 值。具体地，小 A 有一个整数 $D$（$|D| \le V$），他可以选择一些比赛 $1 \le i_1 < i_2 k$，那么在算 $(\sum\limits_{i=1}^{n}p_i)$ 时将 $p_{i_1},p_{i_2},\dots,p_{i_m}$ 都用 $D$ 替代（即不会对 $n \le k$ 的情况和 $n \ge k$ 时 $\text{maxp}$ 的值产生影响）。 为了不暴露，需要保证对于 $1 \le x < m$，均有 $i_{x+1}> i_x + 1$。记 $f(p)$ 为对于一个 perf 值序列 $p_{1\sim n}$，他最后可以修改得到的最大 rating 值。 由于 cobeder 计算每场比赛 perf 值的速度有点慢，所以小 A 只得到了部分比赛的 perf 值。具体地，小 A 得到了一个长度为 $n$ 的序列 $p_{1\sim n}$，其中 $p_i = -7912$ 表示这场比赛的 perf 值还没算出来，但一定是 $[-V,V]$ 中某个整数值。 小 A 想知道，如果给定 $n,k,D,V$ 和 $p_{1\sim n},g_{0\sim kV}$，对于最后所有可能的 perf 值序列 $p_{1\sim n}$，$f(p)$ 的和为多少？答案对 $10^9 + 7$ 取模。

第一行四个整数 $n,k,D,V$。 第二行 $n$ 个整数 $p_{1\sim n}$。 第三行 $kV + 1$ 个整数 $g_{0\sim kV}$。

一行一个整数表示答案。

### 【样例解释 #1】 一种可能的原 perf 序列 $p$ 为 $0,3,-2$，则 $g_{\text{maxp}}=g_3=3$，他的一种最优操作方案是修改 $p_1,p_3$ 为 $2$，则他在这一序列得到的 $f(p)=3(2+3+2)=21$。 ### 数据范围 对于所有数据，满足： - $1 \le k \le 30$。 - $0 \le V \le 30$。 - $|D| \le V$。 - $p_i \in \{-7912\}\cup [-V,V]$ 且 $p_i$ 为整数。 - $1 \le n \le 10^5$。 - $0 \le g_i \le 10^9$ 且对于 $0 \le i < kV$，保证 $g_i \le g_{i+1}$。 ::cute-table{tuack} | $\text{Subtask}$ | $n\le$ | $k \le $ | $V \le $ | $g_i \le $ | 特殊性质 | 分值 | | :--------------: | :----: | :------: | :------: | :--------: | :------------------------------------: | :--: | | #1 | $10^5$ | $30$ | $30$ | $10^9$ | $g_i$ 相同 | $1$ | | #2 | $5$ | $5$ | $5$ | ^ | $n \le k$ | $4$ | | #3 | $30$ | $30$ | $30$ | ^ | 无 | $5$ | | #4 | $500$ | $10$ | $10$ | ^ | ^ | $15$ | | #5 | $10^5$ | $30$ | $30$ | $5$ | ^ | $15$ | | #6 | ^ | $10$ | $10$ | $10^9$ | ^ | $20$ | | #7 | ^ | $30$ | $30$ | ^ | 所有 $p_i = -7912$ 的 $i$ 均满足 $i>k$ | $15$ | | #8 | ^ | ^ | ^ | ^ | 无 | $25$ |