Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

D. Распределение

Задачу добавил: alef

Успешно сдано решений: 13

Распределение
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

А ещё министр науки Фалалей сообщил, что все обучающие курсы будут на онлайн-платформе размещены. Разработана такая в царстве, да вот только простаивает пока без дела. Так что каждый министр должен выделить группу сотрудников, которые будут эти обучающие курсы готовить и размещать на платформе. И специалисты министерства науки этих сотрудников научат, как это делать.

Пришлось каждому из $$$n$$$ министров направить на обучение группу сотрудников. А министерство науки выделило $$$n$$$ аудиторий (по количеству групп). Группы сотрудников имеют разную численность, в группу $$$\#j$$$ входит $$$g_j$$$ сотрудников. Аудитории также могут вмещать различное количество слушателей: в аудитории $$$\#i$$$ может разместиться не более $$$a_i$$$ человек.

Конечно, составители расписания понимают, что группу $$$\#j$$$ можно отправить заниматься в аудиторию $$$\#i$$$ только в том случае, если $$$g_j \le a_i$$$. Их интересует вопрос, сколькими способами можно составить расписание занятий так, чтобы ни одна группа не осталась без аудитории. Гарантируется, что хотя бы один способ составить расписание таким образом существует.

Ваша задача — определить количество способов составить расписание. Поскольку количество может быть довольно большим, выведите ответ по модулю $$$10^9+7$$$.

Входные данные

В первой строке содержится целое число $$$n$$$ $$$(1 \le n \le 3 \cdot 10^5)$$$ — количество групп (оно же — количество аудиторий).

Во второй строке содержатся целые числа $$$g_1, g_2, \ldots, g_n$$$ $$$(1 \le g_j \le 10^6, \, j = 1, 2, \ldots, n)$$$, $$$g_j$$$ — количество людей в группе $$$\#j$$$.

В третьей строке содержатся целые числа $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \le a_i \le 10^6, \, i = 1, 2, \ldots, n)$$$, $$$a_i$$$ — максимально возможное количество слушателей, которое может разместиться в аудитории $$$\#i$$$.

Выходные данные

Выведите единственное целое число — ответ по модулю $$$10^9+7$$$.

Пример

Входные данные
4
8 5 15 12
10 20 20 15
Выходные данные
12

Сдать задачу

Задать вопрос жюри по этой задаче