Matching Mentors

Time limit1sMemory limit1024 MB

Summary

Count the ways to match students with mentors, each student and mentor used at most once, that maximize the minimum final skill across all students.

Level: Medium7 of 10
Topics: Binary search, Greedy, Sorting, Combinatorics
Solved: No attempts yet

Problem

There are $N$ students and $M$ mentors. You want to raise the skills of the students by matching them with mentors.

Student $i$ has skill $A_i$ , and mentor $j$ has leadership $B_j$ . You can match at most one mentor to each student, and each mentor can guide at most one student. A student may also be left without a mentor. When a mentor is matched to a student, that student's skill increases by the mentor's leadership.

Count the number of mentor matching methods that maximize the minimum skill among all students.

Input

The first line contains the number of students $N$ and the number of mentors $M$ , separated by a space. $(1 \leq N, M \leq 200\,000)$

The second line contains the skills of the students $A$ , separated by spaces. $(1 \leq A_i \leq 10^9)$

The third line contains the leadership of the mentors $B$ , separated by spaces. $(1 \leq B_j \leq 10^9)$

Output

Print the number of mentor matching methods that maximize the minimum skill of all students, modulo $10^9 + 7$ .

Examples2

Example 1
Input
```
2 3
3 5
1 3 2
```
Expected output
```
2
```
Example 2
Input
```
4 2
2 5 3 3
5 10
```
Expected output
```
8
```