题目描述

给定长度分别为 $n,m$ 的整数序列 $A,B$ 和常数 $W,d$，序列从 $1$ 开始标号，保证 $A_i,B_i \in [1,W]$。

容易发现，我们有 $\binom{W}{d}$ 种方案选择 $[1,W]$ 中的 $d$ 个互不相同的整数。

对于每一种选择的方案，我们删去 $A$ 中出现的对应的 $d$ 种整数，令此时序列 $B$ 在序列 $A$ 中的出现次数为这次选择方案的权值。

你需要求所有的选择方案的权值和，对 ${10}^9+7$ 取模。

若对题意有疑问，请阅读样例及样例解释。

注：$\binom{a}{b}$ 表示组合数，含义为在 $a$ 个物品中无序地选择出 $b$ 个物品的方案数。

请注意：我们并不会删除序列 $\bm{B}$ 中出现的对应整数。

输入格式

本题有多组数据。

第一行，一个正整数 $T$，表示数据组数。对于每组数据：

第一行，四个正整数 $n, m, W, d$，保证 $d \le W$。

第二行，$n$ 个正整数 $A_1, A_2, \ldots, A_n$，表示序列 $A$。

第三行，$m$ 个正整数 $B_1, B_2, \ldots, B_m$，表示序列 $B$。

输出格式

对于每组数据，输出一个整数表示答案对 ${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

提示

【样例解释】

在样例的第一组数据中：

1. 如果我们选择删去 $A$ 中的字符 $1$，$A$ 将变为 $\{2\}$，此时 $B$ 在 $A$ 中的出现次数为 $0$。
2. 如果我们选择删去 $A$ 中的字符 $2$，$A$ 将变为 $\{1,1,1\}$，此时 $B$ 在 $A$ 中的出现次数为 $2$。
3. 如果我们选择删去 $A$ 中的字符 $3$，$A$ 将变为 $\{1,1,2,1\}$，此时 $B$ 在 $A$ 中的出现次数为 $1$。

因此，第一组数据的答案为 $0+2+1=3$。

再次提醒：我们并不会删除序列 $\bm{B}$ 中出现的对应整数。

---

【数据范围】

对于 $100\%$ 的数据，$1 \le n,m,W \le {10}^6$，$1 \le d, A_i, B_j \le W$，$1 \le T \le 5$。

本题采用捆绑测试且开启子任务依赖！

子任务	$n \le$	$m \le$	$W \le$	特殊性质	分数	依赖
1	$10$		$5$		$10$	\
2	$1000$				$20$	子任务 1
3				A	$15$	\
4				B	$25$
5					$30$	子任务 1、2、3、4

特殊性质 A：保证 $d=1$。

特殊性质 B：令 $c$ 表示仅在序列 $A$ 中出现，而不在序列 $B$ 中出现的数字总数。保证 $c \le 5$。