题目背景

答疑请到：https://www.luogu.org/discuss/show?postid=79498

由于时限等问题，请大家重交一遍这道题

本题时限开至2s

样例：https://files.cnblogs.com/files/ztz11/yl.rar

众所周知，$luogu$有题目难度的评分系统，用户在通过题目后可以选择题目难度以及算法标签，来完善$luogu$的题库

题目描述

$Menteur-Hxy$同学很不老实，为了实现$Noip$前$Ac100$道黑题的目标，他决定雇佣一些水军。

每个水军都有一个能力值$x_i$，表示该水军可以解决难度最高为$x_i$的题目。这些水军十分尽职尽责，在通过这道题目后都会给题目评最高难度。当然，$luogu$的正常用户也会做题，他们会正常的评分。现在，我们给你所有水军的能力值以及每道题正常用户的评分记录，请你求出有多少种选择水军的方案，可以使这道题的评分变为黑题。因为答案可能过大，最终请输出答案数%$p$($p$会在下文中给定)。（难度评定方式及投票方式见下表）

注：$Menteur-Hxy$最少雇佣$1$个水军

评分计算公式：去掉一个最高分，去掉一个最低分后求平均分

(注：并非luogu真正的评分信息，是本人$yy$的)

输入格式

本题有多组输入输出数据

第一行，一个整数$t$,表示数据组数

下面，对于每组数据

第一行，三个整数，$n$，$m$，$p$,表示$Menteur-Hxy$找了$n$个水军，有$m$个$luogu$用户已经评过分，模数为$p$

第二行，$n$个整数，表示水军的能力值

第三行，$m$个整数，表示每个$luogu$用户的投票编号

第四行，1个整数$k$，表示题目的难度系数

输出格式

对于每组数据，输出一个整数，表示方案数取模后的结果，无解请输出$0$

1
5 5 9
1 2 3 4 5
4 5 6 7 8
2

2

提示

样例说明

$luogu$用户评分和为（$25+40+55+75+100=295$），弃掉一个最低分后为$270$，这时$Menteur-Hxy$雇佣两个水军就可以达到目的。合格的水军有$4$个，所以最终答案为$11$

数据范围

对于$30$%的数据，$1<=n,m<=50$

对于另$20$%的数据，$p$为质数

对于$100$%的数据，$1<=n,m<=100000,t<=5,p<=3 \times 10^3$，,确保合格的水军与数量与需要的最少水军数量之差不超过$5000$，且所有输入在$int$范围内

(本题可能轻微卡常？？)

感谢@Ghostcai,@Swhsz帮忙验题