#1449. 串串题
串串题
题目描述
给定长度分别为 的整数序列 和常数 ,序列从 开始标号,保证 。
容易发现,我们有 种方案选择 中的 个互不相同的整数。
对于每一种选择的方案,我们删去 中出现的对应的 种整数,令此时序列 在序列 中的出现次数为这次选择方案的权值。
你需要求所有的选择方案的权值和,对 取模。
若对题意有疑问,请阅读样例及样例解释。
注: 表示组合数,含义为在 个物品中无序地选择出 个物品的方案数。
请注意:我们并不会删除序列 中出现的对应整数。
输入格式
本题有多组数据。
第一行,一个正整数 ,表示数据组数。对于每组数据:
第一行,四个正整数 ,保证 。
第二行, 个正整数 ,表示序列 。
第三行, 个正整数 ,表示序列 。
输出格式
对于每组数据,输出一个整数表示答案对 取模的结果。
样例
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