Олимпиадный тренинг

Задача . A. Подсчет порядка


Задача

Темы: Комбинаторика математика *1100 сортировки

Даны два массива \(a\) и \(b\), каждый из \(n\) целых чисел. Все элементы \(a\) попарно различны.

Найдите количество способов переставить элементы массива \(a\) так, чтобы выполнялось \(a_i > b_i\) для всех \(1 \le i \le n\), по модулю \(10^9 + 7\).

Два способа перестановки считаются разными, если полученные массивы различны.

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

Каждый тест содержит несколько наборов входных данных. Первая строка содержит количество наборов входных данных \(t\) (\(1 \le t \le 10^4\)). Далее следует их описание.

Первая строка каждого набора входных данных содержит одно целое число \(n\) (\(1 \le n \le 2 \cdot 10^{5}\)) — длину массива \(a\) и \(b\).

Вторая строка каждого набора входных данных содержит \(n\) различных целых чисел \(a_1\), \(a_2\), \(\ldots\), \(a_n\) (\(1 \le a_i \le 10^9\)) — массив \(a\). Гарантируется, что все элементы \(a\) попарно различны.

Третья строка каждого набора входных данных содержит \(n\) целых чисел \(b_1\), \(b_2\), \(\ldots\), \(b_n\) (\(1 \le b_i \le 10^9\)) — массив \(b\).

Гарантируется, что сумма \(n\) по всем наборам входных данных не превышает \(2 \cdot 10^{5}\).

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

Для каждого набора входных данных выведите количество способов переставить элементы массива \(a\) так, чтобы выполнялось \(a_i > b_i\) для всех \(1 \le i \le n\), по модулю \(10^9 + 7\).


Примеры
№Входные данныеВыходные данные
1 
5
6
9 6 8 4 5 2
4 1 5 6 3 1
3
4 3 2
3 4 9
1
2
1
3
2 3 4
1 3 3
12
2 3 7 10 23 28 29 50 69 135 420 1000
1 1 2 3 5 8 13 21 34 55 89 144
 
32
0
1
0
13824

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++3
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет