P17317 [KismetOI 2026 I] Cheating

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$.

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 one integer in one line, representing the answer.

### 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