#1449. 串串题

串串题

题目描述

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

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

对于每一种选择的方案,我们删去 AA 中出现的对应的 dd 种整数,令此时序列 BB 在序列 AA 中的出现次数为这次选择方案的权值。

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

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

注:(ab)\binom{a}{b} 表示组合数,含义为在 aa 个物品中无序地选择出 bb 个物品的方案数。

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

输入格式

本题有多组数据。

第一行,一个正整数 TT,表示数据组数。对于每组数据:

第一行,四个正整数 n,m,W,dn, m, W, d,保证 d≤Wd \le W。

第二行,nn 个正整数 A1,A2,…,AnA_1, A_2, \ldots, A_n,表示序列 AA。

第三行,mm 个正整数 B1,B2,…,BmB_1, B_2, \ldots, B_m,表示序列 BB。

输出格式

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

题目来源:洛谷 P9149