Problem Description

Menteur-Hxy is not very honest. To achieve the goal of solving 100 black-level problems before NOIp, he decides to hire some water army, with a minimum of 1 water army member.

Each water army member has a capability value \( x_i \), indicating that they can solve problems up to a difficulty of \( x_i \). These water army members are very diligent and will rate the problem at the highest difficulty after solving it. Of course, regular users of luogu will also solve problems and rate them normally. Now, we provide you with the capability values of all water army members and the rating records of regular users for each problem. You are asked to calculate how many ways there are to select water army members such that the rating of the problem becomes black-level. Since the answer may be very large, output the answer modulo \( p \).

The rating calculation formula is: remove one highest score and one lowest score, then calculate the average.

[Table 1: Voting Information]

[Table 2: Difficulty Rules]

Input Format

This problem contains multiple test cases.

The first line contains an integer \( T \), the number of test cases.

For each test case:

• The first line contains three integers \( n, m, p \), representing the number of water army members Menteur-Hxy hired, the number of luogu user ratings, and the modulo number for output.
• The second line contains \( n \) integers \( s_1 \ldots s_n \), representing the capability values of the water army members.
• The third line contains \( m \) integers \( t_1 \ldots t_m \), representing the vote IDs of each luogu user.
• The fourth line contains an integer \( k \), representing the difficulty coefficient of the problem.

Output Format

For each test case, output one line containing an integer, which is the total number of selection schemes modulo \( p \). If there is no solution, output 0.

Sample Input and Output

Input Sample #1

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

Output Sample #1

2

Input Sample #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

Output Sample #2

1023
1023
1023
15
1023

Notes/Hints

[Sample Explanation 1]

The sum of luogu user ratings is \( 25 + 40 + 55 + 75 + 100 = 295 \). After discarding one lowest score, it becomes 270. At this point, Menteur-Hxy can achieve his goal by hiring two or more water army members.

Since there are 4 water army members who can pass the problem, the total number of selection schemes is:

\[ \{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\} \]

A total of 11 schemes, modulo 9 results in 2.

[Data Scale and Constraints]

For 30% of the data, \( n, m \leq 50 \).

For another 20% of the data, \( p \) is a prime number.

For 100% of the data, \( 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 \).

The difference between the number of qualified water army members and the minimum required number of water army members does not exceed 5000.

(Note: This problem may have a slight time limit issue. Thanks to @Ghostcai and @Swhsz for helping with problem verification.)

见题面 Input 部分

见题面 Output 部分