Problem Description

cobeder has started holding rated contests. Little A participated in $n$ contests, and the perf value of the $i$-th contest is $p_i$ ($|p_i| \le V$). The cobeder system has a constant $k$ and an array $g_{0 \sim kV}$. Little A’s rating can be computed as follows:

• If $n \le k$, then the rating equals $g_{\max\limits_{i=0}^{n}(\sum\limits_{j=1}^{i}p_j)}$.
• If $n > k$, let $\text{maxp} = \max\limits_{i=0}^{k}(\sum\limits_{j=1}^{i}p_j)$. Then the rating equals $g_{\text{maxp}} \times (\sum\limits_{i=1}^{n}p_i)$.

In particular, when $i=0$, set $\sum\limits_{j=1}^{i}p_j=0$.

Little A hacked into cobeder’s system and wants to take this chance to modify his rating. Specifically, Little A has an integer $D$ ($|D| \le V$). He may choose some contests $1 \le i_1 < i_2 < i_3 < \dots < i_m \le n$ such that, when computing the rating and if $n > k$, during the computation of $(\sum\limits_{i=1}^{n}p_i)$, the values $p_{i_1}, p_{i_2}, \dots, p_{i_m}$ are all replaced by $D$ (that is, it does not affect the case $n \le k$, nor does it affect the value of $\text{maxp}$ when $n \ge k$).

To avoid being exposed, it must hold that for $1 \le x < m$, $i_{x+1} > i_x + 1$. Let $f(p)$ denote, for a perf sequence $p_{1\sim n}$, the maximum rating value he can finally obtain after modifications.

Since cobeder computes the perf value of each contest a bit slowly, Little A only obtained some of the perf values. Specifically, Little A got a sequence $p_{1\sim n}$ of length $n$, where $p_i = -7912$ means the perf value for this contest has not been computed yet, but it must be some integer in $[-V, V]$.

Little A wants to know: given $n, k, D, V$ and $p_{1\sim n}, g_{0\sim kV}$, over all possible final perf sequences $p_{1\sim n}$, what is the sum of $f(p)$? Output the answer modulo $10^9 + 7$.

Input Format

The first line contains four integers $n, k, D, V$.

The second line contains $n$ integers $p_{1\sim n}$.

The third line contains $kV + 1$ integers $g_{0\sim kV}$.

Output Format

Output one integer in one line, representing the answer.

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

Hint

Sample Explanation #1

One possible original perf sequence $p$ is $0, 3, -2$. Then $g_{\text{maxp}} = g_3 = 3$. One optimal operation is to modify $p_1, p_3$ to $2$, and then for this sequence, $f(p) = 3(2+3+2)=21$.

Constraints

For all data, it holds that:

• $1 \le k \le 30$.
• $0 \le V \le 30$.
• $|D| \le V$.
• $p_i \in \{-7912\}\cup [-V,V]$ and each $p_i$ is an integer.
• $1 \le n \le 10^5$.
• $0 \le g_i \le 10^9$, and for $0 \le i < kV$, it is guaranteed that $g_i \le g_{i+1}$.

::cute-table{tuack} | $\text{Subtask}$ | $n\le$ | $k \le$ | $V \le$ | $g_i \le$ | Special Properties | Score | | :--------------: | :----: | :------: | :------: | :--------: | :----------------: | :--: | | #1 | $10^5$ | $30$ | $30$ | $10^9$ | All $g_i$ are the same. | $1$ | | #2 | $5$ | $5$ | $5$ | ^ | $n \le k$. | $4$ | | #3 | $30$ | $30$ | $30$ | ^ | None. | $5$ | | #4 | $500$ | $10$ | $10$ | ^ | ^ | $15$ | | #5 | $10^5$ | $30$ | $30$ | $5$ | ^ | $15$ | | #6 | ^ | $10$ | $10$ | $10^9$ | ^ | $20$ | | #7 | ^ | $30$ | $30$ | ^ | For all $i$ with $p_i = -7912$, it holds that $i > k$. | $15$ | | #8 | ^ | ^ | ^ | ^ | None. | $25$ |

Translated by ChatGPT 5