Problem Description

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

Input Format

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

Output Format

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

2
4 2 3 1
1 1 2 1
1 1
8 3 4 1
1 2 3 1 2 3 1 2
1 2 1

3
2

Hint

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

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