P9149 Skewer Problem.

Given two integer sequences $A$ and $B$ of lengths $n$ and $m$, and constants $W$ and $d$, the sequences are indexed starting from $1$. It is guaranteed that $A_i, B_i \in [1,W]$. It is easy to see that there are $\binom{W}{d}$ ways to choose $d$ pairwise distinct integers from $[1,W]$. For each choice, we delete from $A$ all occurrences of the corresponding $d$ integers. Let the number of times sequence $B$ occurs in sequence $A$ at this time be the weight of this choice. You need to compute the sum of the weights over all choices, modulo ${10}^9+7$. If you are unsure about the statement, please read the samples and the sample explanation. Note: $\binom{a}{b}$ denotes a binomial coefficient, meaning the number of ways to choose $b$ items from $a$ items **without order**. **Please note: we will not delete the corresponding integers that appear in sequence $\bm{B}$.**

**This problem contains multiple test cases.** The first line contains a positive integer $T$, the number of test cases. For each test case: The first line contains four positive integers $n, m, W, d$, with $d \le W$. The second line contains $n$ positive integers $A_1, A_2, \ldots, A_n$, representing sequence $A$. The third line contains $m$ positive integers $B_1, B_2, \ldots, B_m$, representing sequence $B$.

For each test case, output one integer: the answer modulo ${10}^9+7$.

**Sample Explanation** In the first test case of the sample: 1. If we choose to delete the number $1$ from $A$, then $A$ becomes $\{2\}$, and the number of occurrences of $B$ in $A$ is $0$. 1. If we choose to delete the number $2$ from $A$, then $A$ becomes $\{1,1,1\}$, and the number of occurrences of $B$ in $A$ is $2$. 1. If we choose to delete the number $3$ from $A$, then $A$ becomes $\{1,1,2,1\}$, and the number of occurrences of $B$ in $A$ is $1$. Therefore, the answer for the first test case is $0+2+1=3$. **Reminder again: we will not delete the corresponding integers that appear in sequence $\bm{B}$.** --- **Constraints** For $100\%$ of the data, $1 \le n,m,W \le {10}^6$, $1 \le d, A_i, B_j \le W$, and $1 \le T \le 5$. **This problem uses bundled testdata and enables subtask dependencies.** | Subtask | $n \le$ | $m \le$ | $W \le$ | Special Property | Score | Dependency | | - | - | - | - | - | - | - | | 1 | $10$ | $10$ | $5$ | | $10$ | \ | | 2 | $1000$ | $1000$ | $5$ | | $20$ | Subtask 1 | | 3 | | | | A | $15$ | \ | | 4 | | | | B | $25$ | \ | | 5 | | | | | $30$ | Subtask 1, 2, 3, 4 | Special Property A: guaranteed that $d=1$. Special Property B: let $c$ be the total number of values that appear only in sequence $A$ but do not appear in sequence $B$. It is guaranteed that $c \le 5$. Translated by ChatGPT 5