Сплячі корови#10373

Сплячі корови

1 секунда

128 мегабайтів

Легка

Фермер Джон має $n$ корів різних розмірів. Спочатку він збудував для кожної корови окремий хлів, але тепер деякі корови виросли і не поміщаються в свої хліви. Спочатку ФД збудував $n$ хлівів розміром $t_{1}$ t_1, $t_{2}$ t_2, ..., $t_{n}$ t_n, тоді як корови тепер мають розміри $s_{1}$ s_1, $s_{2}$ s_2, ..., $s_{n}$ s_n ( $1 \leq s_{i}, t_{i} \leq 1 0^{9}$ 1 \le s_i, t_i \le 10^9).

Кожної ночі корови виконують ритуал пошуку хліва для сну. Корова $i$ може спати в хліві $j$ лише тоді, коли вона в нього поміщається ( $s_{i} \leq t_{j}$ s_i \le t_j). У кожному хліві може бути не більше однієї корови.

Зіставлення корів з хлівами вважається максимальним, якщо кожна корова, якій призначено хлів, може в ньому поміститися, а кожна корова, якій не призначено хлів, не може поміститися в жоден з вільних хлівів.

Потрібно обчислити максимальну кількість таких зіставлень за модулем $1 0^{9} + 7$ 10^9 + 7.

Вхідні дані

Перший рядок містить число $n$ ( $1 \leq n \leq 3000$ 1 \le n \le 3000). Другий рядок містить $n$ цілих чисел $s_{1}$ s_1, $s_{2}$ s_2, ..., $s_{n}$ s_n. Третій рядок містить $n$ цілих чисел $t_{1}$ t_1, $t_{2}$ t_2, ..., $t_{n}$ t_n.

Вихідні дані

Виведіть максимальну кількість зіставлень за модулем $1 0^{9} + 7$ 10^9 + 7.

Приклади

Ось список усіх дев'яти максимальних відповідностей. Упорядкована пара ( $i$ , $j$ ) означає, що корові $i$ призначено хлів $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)

Приклад 1