310402: CF1828C. Counting Orders

C. 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

题目大意：
题目C：计算顺序

给你两个各含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
```题目大意： 题目C：计算顺序 给你两个各含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 ```