P4993 评分系统

答疑请到：https://www.luogu.org/discuss/show?postid=79498 由于时限等问题，请大家重交一遍这道题 本题时限开至2s 样例：https://files.cnblogs.com/files/ztz11/yl.rar --- 众所周知，luogu 有题目难度的评分系统，用户在通过题目后可以选择题目难度以及算法标签，来完善 luogu 的题库。  （原注：以下内容非真实评分数据，纯属作者编造，仅供娱乐使用。）

Menteur-Hxy 同学很不老实，为了实现 NOIp 前 AC $100$ 道黑题的目标，他决定雇佣一些水军，最少雇佣 $1$ 个水军。 每个水军都有一个能力值 $x_i$，表示该水军可以解决难度最高为 $x_i$ 的题目。这些水军十分尽职尽责，在通过这道题目后都会给题目评最高难度。当然，luogu 的正常用户也会做题，他们会正常地评分。现在，我们给你所有水军的能力值以及每道题正常用户的评分记录，请你求出有多少种选择水军的方案，可以使这道题的评分变为黑题。因为答案可能过大，最终请输出答案数 $\bmod p$ 的值。 评分计算公式：去掉一个最高分，去掉一个最低分后求平均分。 **【表一：投票信息】** | 投票编号 | 对应难度 | 分数贡献 | | :------: | :------: | :------: | | $1$ | 入门 | $1$ | | $2$ | 普及- | $10$ | | $3$ | 普及/提高- | $15$ | | $4$ | 普及+/提高 | $25$ | | $5$ | 提高+/省选- | $40$ | | $6$ | 省选/NOI- | $55$ | | $7$ | NOI | $75$ | | $8$ | NOI+/CTSC | $100$ | **【表二：难度规则】** | 难度等级 | 对应颜色 | 对应分数 | | :------: | :------: | :------: | | 入门 | 红 | $1\sim 5$ | | 普及- | 橙 | $6\sim 12$ | | 普及/提高- | 黄 | $13\sim 20$ | | 普及+/提高 | 绿 | $21\sim 35$ | | 提高+/省选- | 蓝 | $36\sim 45$ | | 省选/NOI- | 紫 | $46\sim 70$ | | NOI+/CTSC | 黑 | $71\sim 100$ |

**本题有多组数据。** 第一行，一个整数 $T$，表示数据组数。 对于每组数据： + 第一行三个整数 $n, m, p$，分别表示 Menteur-Hxy 找的水军数量，luogu 用户评分数量，和输出时的模数。 + 第二行，$n$ 个整数 $s_1 \dots s_n$ 分别表示水军的能力值。 + 第三行，$m$ 个整数 $t_1 \dots t_n$，表示每个 luogu 用户的投票编号。 + 第四行，一个整数 $k$ ，表示题目的难度系数。

对于每组数据，输出一行一个整数，表示总选择方案数对 $p$ 取模后的结果，如无解，则输出 $0$。

**【样例解释 $1$】** luogu 用户评分和为 $25+40+55+75+100=295$，弃掉一个最低分后为 $270$，这时 Menteur-Hxy 雇佣两个及以上水军就可以达到目的。 因为可以通过本题的水军共有 $4$ 个，所以选择方案共有： $$\{1,2\}\{1,2,3\}\{1,2,3,4\}\{1,2,4\}\{1,3\}\{1,3,4\}\{1,4\}\{2,3\}\{2,3,4\}\{2,4\}\{3,4\}$$ 共 $11$ 种，对 $9$ 取余后结果为 $2$。 **【数据规模与约定】** 对于 $30\%$ 的数据，$n, m \leq 50$。 对于另外 $20\%$ 的数据，$p$ 为质数。 对于 $100\%$ 的数据，$1 \leq n, m, k,s_i \leq 10^5, 1 \leq t \leq 5, 2 \leq p \leq 3 \times 10^3, 1 \leq t_i \leq 8$。 保证合格水军的数量与需要的最少水军数量之差不超过 $5000$。 （原注：本题可能轻微卡常。感谢 @Ghostcai ，@Swhsz 帮忙验题。）