串串题

给定长度分别为 $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$。 1. 如果我们选择删去 $A$ 中的字符 $2$，$A$ 将变为 $\{1,1,1\}$，此时 $B$ 在 $A$ 中的出现次数为 $2$。 1. 如果我们选择删去 $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$ | $10$ | $5$ | | $10$ | \ | | 2 | $1000$ | $1000$ | $5$ | | $20$ | 子任务 1 | | 3 | | | | A | $15$ | \ | | 4 | | | | B | $25$ | \ | | 5 | | | | | $30$ | 子任务 1、2、3、4 | 特殊性质 A：保证 $d=1$。 特殊性质 B：令 $c$ 表示仅在序列 $A$ 中出现，而不在序列 $B$ 中出现的数字总数。保证 $c \le 5$。