Problem Description

Farmer John has $N$ cows of various sizes ($1 \le N \le 3000$). He originally custom-built a stall for each cow, but now some cows have grown, so the original stall sizes are no longer sufficient. Specifically, FJ originally built $N$ stalls with sizes $t_1, t_2, \ldots, t_N$, and the cows now have sizes $s_1, s_2, \ldots, s_N$ ($1 \le s_i, t_i \le 10^9$).

Every night, the cows find stalls to sleep in in some way. Cow $i$ can sleep in stall $j$ if and only if her size can fit into the stall ($s_i \le t_j$). Each stall can have at most one cow sleeping in it.

We say a matching between cows and stalls is maximal if and only if every assigned cow can fit into her assigned stall, and for every cow that is not assigned a stall, she cannot fit into any unassigned empty stall.

Compute the number of maximal matchings modulo $10^9 + 7$.

Input Format

The first line contains $N$.

The second line contains $N$ space-separated integers $s_1, s_2, \ldots, s_N$.

The third line contains $N$ space-separated integers $t_1, t_2, \ldots, t_N$.

Output Format

Output the number of maximal matchings modulo $10^9 + 7$.

4
1 2 3 4
1 2 2 3

9

Hint

Below are all nine maximal matchings. The ordered pair $(i, j)$ means cow $i$ is assigned to stall $j$.

(1, 1), (2, 2), (3, 4)
(1, 1), (2, 3), (3, 4)
(1, 1), (2, 4)
(1, 2), (2, 3), (3, 4)
(1, 2), (2, 4)
(1, 3), (2, 2), (3, 4)
(1, 3), (2, 4)
(1, 4), (2, 2)
(1, 4), (2, 3)

• In testdata 2-3, $N \le 8$.
• In testdata 4-12, $N \le 50$.
• In testdata 13-20, there are no additional constraints.

Problem provided by: Nick Wu.

Translated by ChatGPT 5