题目描述

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 <i_3 < \dots < i_m \le n$，使得在计算 rating 时如果 $n > 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}$。

输出格式

一行一个整数表示答案。

3 2 2 3
-7912 3 -2
1 1 2 3 4 5 5

152

5 2 2 3
-1 3 -2 -7912 -7912
0 0 2 3 3 4 5

900

5 2 2 3
-7912 3 -2 -7912 -7912
0 0 2 3 3 4 5

7895

5 7 2 5
-5 -7912 0 -7912 -7912 
0 0 0 168 303 303 508 508 508 690 690 828 828 828 1005 1005 1005 1190 1190 1190 1190 1190 1190 1217 1217 1287 1600 1600 1600 1600 1600 1600 1600 1600 1600 1600

45661

提示

【样例解释 #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$ |