310393: CF1827A. Counting Orders

A. Counting Orderstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given two arrays $a$ and $b$ each consisting of $n$ integers. All elements of $a$ are pairwise distinct.

Find the number of ways to reorder $a$ such that $a_i > b_i$ for all $1 \le i \le n$, modulo $10^9 + 7$.

Two ways of reordering are considered different if the resulting arrays are different.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^{5}$) — the length of the array $a$ and $b$.

The second line of each test case contains $n$ distinct integers $a_1$, $a_2$, $\ldots$, $a_n$ ($1 \le a_i \le 10^9$) — the array $a$. It is guaranteed that all elements of $a$ are pairwise distinct.

The second line of each test case contains $n$ integers $b_1$, $b_2$, $\ldots$, $b_n$ ($1 \le b_i \le 10^9$) — the array $b$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^{5}$.

Output

For each test case, output the number of ways to reorder array $a$ such that $a_i > b_i$ for all $1 \le i \le n$, modulo $10^9 + 7$.

ExampleInput

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

Output

32
0
1
0
13824

题目大意：
题目名为“A. 计算顺序”，给定两个各含有n个整数的数组a和b，数组a中的所有元素都是两两不同的。需要找出将数组a重新排序的方式的数量，使得对于所有1≤i≤n，都有a_i > b_i，结果对10^9 + 7取模。如果两种重新排序方式得到的结果数组不同，则认为这两种方式是不同的。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。
- 每个测试用例的描述如下：
- 第一行包含一个整数n（1≤n≤2×10^5），表示数组a和b的长度。
- 第二行包含n个不同的整数a_1, a_2, …, a_n（1≤a_i≤10^9），表示数组a。保证a中的所有元素都是两两不同的。
- 第三行包含n个整数b_1, b_2, …, b_n（1≤b_i≤10^9），表示数组b。
- 保证所有测试用例的n之和不超过2×10^5。

输出：
- 对于每个测试用例，输出一个整数，表示将数组a重新排序的方式的数量，使得对于所有1≤i≤n，都有a_i > b_i，结果对10^9 + 7取模。

示例：
输入：
```
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
```题目大意： 题目名为“A. 计算顺序”，给定两个各含有n个整数的数组a和b，数组a中的所有元素都是两两不同的。需要找出将数组a重新排序的方式的数量，使得对于所有1≤i≤n，都有a_i > b_i，结果对10^9 + 7取模。如果两种重新排序方式得到的结果数组不同，则认为这两种方式是不同的。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。 - 每个测试用例的描述如下： - 第一行包含一个整数n（1≤n≤2×10^5），表示数组a和b的长度。 - 第二行包含n个不同的整数a_1, a_2, …, a_n（1≤a_i≤10^9），表示数组a。保证a中的所有元素都是两两不同的。 - 第三行包含n个整数b_1, b_2, …, b_n（1≤b_i≤10^9），表示数组b。 - 保证所有测试用例的n之和不超过2×10^5。 输出： - 对于每个测试用例，输出一个整数，表示将数组a重新排序的方式的数量，使得对于所有1≤i≤n，都有a_i > b_i，结果对10^9 + 7取模。 示例： 输入： ``` 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 ```