题目背景

答疑请到：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
5 5 9
1 2 3 4 5
4 5 6 7 8
2

2

5
20 10 1329
540 499 490 419 308 261 323 476 476 374 23 13 14 16 19 34 43 19 27 32 
8 8 8 8 8 7 7 7 7 7 
50
20 10 1800
74 434 97 134 283 118 234 498 328 388 29 48 48 43 23 42 31 16 20 26 
8 8 7 6 8 8 8 7 7 7 
50
20 10 2704
142 378 330 281 377 64 340 309 466 289 34 37 19 17 20 48 21 28 38 15 
6 8 6 6 8 7 7 7 7 6 
50
20 10 72
365 356 456 479 459 222 548 377 212 223 38 20 49 18 49 38 31 48 41 17 
6 8 7 6 8 7 8 8 8 6 
50
20 10 1416
367 191 403 298 445 464 79 467 431 362 10 45 48 37 46 43 11 35 30 39 
8 6 8 7 7 7 8 8 7 8 
50

1023
1023
1023
15
1023

提示

【样例解释 $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 帮忙验题。）