P7154 [USACO20DEC] Sleeping Cows P

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$.

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 the number of maximal matchings modulo $10^9 + 7$.

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