Counting Maximal Matchings in Threshold Barns

Farmer John originally built N barns (numbered 1 through N) with capacities t₁, t₂, …, t_N, each designed for one cow, and he owned N cows with sizes s₁, s₂, …, s_N. Unfortunately, some cows have grown so large that they no longer fit into the barn originally built for them. A cow i can sleep in barn j if and only if

\( s_i \le t_j \).

Each barn can accommodate at most one cow. Every night, the cows choose a set of barns in which to sleep, thereby forming a matching between cows and barns. A matching is called maximal if:

• Every cow assigned to a barn fits in her barn, and
• for every cow that is not assigned to any barn, there is no free barn available in which she would fit (i.e. for every free barn j and every unmatched cow i, it holds that \( s_i > t_j \)).

Your task is to compute the total number of maximal matchings modulo \(10^9+7\).

Input Format: The first line contains a single integer N (\(1 \le N \le 3000\)). The second line contains N integers \(s_1, s_2, \dots, s_N\) (\(1 \le s_i \le 10^9\)). The third line contains N integers \(t_1, t_2, \dots, t_N\) (\(1 \le t_i \le 10^9\)).

Output Format: Output a single integer, the number of maximal matchings modulo \(10^9+7\).

Note: In a maximal matching, if some cow is not assigned a barn then every barn that is free must be too small for that cow. In other words, the set of unmatched cows and free barns obey a natural threshold condition.

Example:

Input:
2
10 100
1 100

Output:
1

In the example, only one maximal matching is possible: assign cow 2 to barn 2 (since 100 \(\le\) 100) and leave cow 1 unmatched. Although cow 1 fits in barn 1 (10 \(\le\) 1 is false), barn 1 is free but too small (1 < 10), so the matching is maximal.

Note to contestants: Although the constraints allow N up to 3000, an efficient solution requires advanced dynamic programming or combinatorial techniques. For the purposes of this problem statement and sample test cases, you may assume that the input sizes are small. In a real contest setting you will need to design an algorithm efficient enough for the full constraints.

inputFormat

The input consists of three lines. The first line contains an integer N. The second line contains N space‐separated integers \(s_1, s_2, \dots, s_N\). The third line contains N space‐separated integers \(t_1, t_2, \dots, t_N\).

outputFormat

Output a single integer representing the number of maximal matchings mod \(10^9+7\).

sample

2
10 100
1 100

1