It was a rainy autumn day. A total of n students attended an olympiad, their intelligence can be ranked with integers ai. And what a coincidence! Jury prepared exactly n problems, their difficulty can be ranked with integers bi.
A student can solve a problem if and only if their intelligence ai is greater or equal than the difficulty bj of the problem. Jury don’t want to upset participants, so each participant was given one problem they can solve.
Count the amount of ways to distribute problems between students, so that everyone is able to solve the problem they got. Each student should get exactly one problem, and each problem should be given to exactly one student. The answer can be large, so divide the answer by p and output the remainer (compute the answer modulo p).
Input
The first line contains a single integer n — the amount of participants (1 ≤ n ≤ 105).
The second line contains n space-separated integers ai — values of intelligence of participants (0 ≤ ai ≤ 109).
The third line contains n space-separated integers bi — values of difficulty of problems (0 ≤ bi ≤ 109).
The fourth line contains one integer p (1 ≤ p ≤ 109).
Output
Output a single integer — the amount of ways to distribute the problems according to the statement modulo p.
Samples
input | output |
---|
3
1 2 3
1 2 3
100
| 1
|
3
3 3 3
1 1 1
100
| 6
|
Problem Author: Valintin Zuev
Problem Source: Ural School Programming Contest 2019