ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural Regional School Programming Contest 2019

About     Problems     Submit solution     Judge status     Standings
Contest is over

H. Olympiad for Everyone

Time limit: 3.0 second
Memory limit: 256 MB
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

inputoutput
3
1 2 3
1 2 3
100
1
3
3 3 3
1 1 1
100
6
Problem Author: Valintin Zuev
To submit the solution for this problem go to the Problem set: 2145. Olympiad for Everyone