{"raw_statement":[{"iden":"statement","content":"给定长度分别为 $n,m$ 的整数序列 $A,B$ 和常数 $W,d$，序列从 $1$ 开始标号，保证 $A_i,B_i \\in [1,W]$。\n\n容易发现，我们有 $\\binom{W}{d}$ 种方案选择 $[1,W]$ 中的 $d$ 个互不相同的整数。\n\n对于每一种选择的方案，我们删去 $A$ 中出现的对应的 $d$ 种整数，令此时序列 $B$ 在序列 $A$ 中的出现次数为这次选择方案的权值。\n\n你需要求所有的选择方案的权值和，对 ${10}^9+7$ 取模。\n\n若对题意有疑问，请阅读样例及样例解释。\n\n注：$\\binom{a}{b}$ 表示组合数，含义为在 $a$ 个物品中**无序**地选择出 $b$ 个物品的方案数。\n\n**请注意：我们并不会删除序列 $\\bm{B}$ 中出现的对应整数。**"},{"iden":"input","content":"**本题有多组数据。**\n\n第一行，一个正整数 $T$，表示数据组数。对于每组数据：\n\n第一行，四个正整数 $n, m, W, d$，保证 $d \\le W$。\n\n第二行，$n$ 个正整数 $A_1, A_2, \\ldots, A_n$，表示序列 $A$。\n\n第三行，$m$ 个正整数 $B_1, B_2, \\ldots, B_m$，表示序列 $B$。"},{"iden":"output","content":"对于每组数据，输出一个整数表示答案对 ${10}^9+7$ 取模的结果。"},{"iden":"note","content":"**【样例解释】**\n\n在样例的第一组数据中：\n\n1. 如果我们选择删去 $A$ 中的字符 $1$，$A$ 将变为 $\\{2\\}$，此时 $B$ 在 $A$ 中的出现次数为 $0$。\n1. 如果我们选择删去 $A$ 中的字符 $2$，$A$ 将变为 $\\{1,1,1\\}$，此时 $B$ 在 $A$ 中的出现次数为 $2$。\n1. 如果我们选择删去 $A$ 中的字符 $3$，$A$ 将变为 $\\{1,1,2,1\\}$，此时 $B$ 在 $A$ 中的出现次数为 $1$。\n\n因此，第一组数据的答案为 $0+2+1=3$。\n\n**再次提醒：我们并不会删除序列 $\\bm{B}$ 中出现的对应整数。**\n\n---\n\n**【数据范围】**\n\n对于 $100\\%$ 的数据，$1 \\le n,m,W \\le {10}^6$，$1 \\le d, A_i, B_j \\le W$，$1 \\le T \\le 5$。\n\n**本题采用捆绑测试且开启子任务依赖！**\n\n| 子任务 | $n \\le$ | $m \\le$ | $W \\le$ | 特殊性质 | 分数 | 依赖 |\n| - | - | - | - | - | - | - |\n| 1 | $10$ | $10$ | $5$ | | $10$ | \\ |\n| 2 | $1000$ | $1000$ | $5$ | | $20$ | 子任务 1 |\n| 3 |  | | | A | $15$ | \\ |\n| 4 |  | | | B | $25$ | \\ |\n| 5 | | | | | $30$ | 子任务 1、2、3、4 |\n\n特殊性质 A：保证 $d=1$。\n\n特殊性质 B：令 $c$ 表示仅在序列 $A$ 中出现，而不在序列 $B$ 中出现的数字总数。保证 $c \\le 5$。"}],"translated_statement":null,"sample_group":[["2\n4 2 3 1\n1 1 2 1\n1 1\n8 3 4 1\n1 2 3 1 2 3 1 2\n1 2 1\n","3\n2\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}