멘토 매칭하기

시간 제한1초메모리 제한1024 MB

요약

학생 실력과 멘토 지도력이 주어질 때 멘토를 학생에게 일대일로 매칭해 실력 최솟값을 최대로 만들고, 그렇게 만드는 매칭의 수를 센다.

난이도: 어려움10점 중 8점
유형: 그리디, 정렬, 조합론, 수학
정답자: 아직 제출이 없습니다

문제

학생 $N$ 명, 멘토 $M$ 명이 존재한다. 당신은 학생들의 실력을 높여주기 위해 멘토를 매칭해주려고 한다.

$i$ 번 학생은 실력 $A\_i$ 를 가지고 있으며, $j$ 번 멘토는 지도력 $B\_j$ 를 가지고 있다. 학생 한 명에게는 최대 한 명의 멘토를 매칭해줄 수 있고, 각 멘토 역시 최대 한 명의 학생을 지도해줄 수 있다. 학생에게 멘토를 매칭하지 않을 수도 있다. 멘토가 매칭된 학생의 실력은 해당 멘토의 지도력만큼 늘어난다.

모든 학생의 실력의 최솟값을 최대화시키는 멘토 매칭 방법의 수를 알아보자.

입력

첫째 줄에 학생의 수 $N$ , 멘토의 수 $M$ 이 공백으로 구분되어 정수로 주어진다. $(1 \leq N, M \leq 200\\,000)$

둘째 줄에 학생의 실력을 나타내는 수열 $A$ 가 공백으로 구분되어 정수로 주어진다. $(1 \leq A\_i \leq 10^9)$

셋째 줄에 멘토의 지도력을 나타내는 수열 $B$ 가 공백으로 구분되어 정수로 주어진다. $(1 \leq B\_j \leq 10^9)$

출력

첫째 줄에 모든 학생의 실력의 최솟값을 최대화하는 멘토 매칭 방법의 수를 $1\\,000\\,000\\,007 \\,(10^9 + 7)$ 으로 나눈 나머지를 출력한다.

예제2

예제 1
입력
```
2 3
3 5
1 3 2
```
예상 출력
```
2
```
예제 2
입력
```
4 2
2 5 3 3
5 10
```
예상 출력
```
8
```