企业官网建设流程全解析

time limit per test

1 second

memory limit per test

256 megabytes

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 ai>bi for all 1≤i≤n, modulo 109+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≤t≤104). The description of the test cases follows.

The first line of each test case contains a single integer n (1≤n≤2⋅105) — the length of the array a and b.

The second line of each test case contains n distinct integers a1, a2, …, an (1≤ai≤109) — the array a. It is guaranteed that all elements of a are pairwise distinct.

The second line of each test case contains n integers b1, b2, …, bn (1≤bi≤109) — the array b.

It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.

Output

For each test case, output the number of ways to reorder array a such that ai>bi for all 1≤i≤n, modulo 109+7.

Example

Input

Copy

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

Copy

32 0 1 0 13824

解题说明：此题是一道数学题，采用贪心算法，首先对数列a和b分别排序，从最大的b开始，对于每个b[j]，计算有多少个a元素可以配对，答案就是所有选择数的乘积。

#include<iostream> #include<algorithm> using namespace std; const int N = 2e5 + 5, M = 1e9 + 7; int t, n, a[N], b[N], f[N]; int main() { cin >> t; while (t--) { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } sort(a + 1, a + n + 1); for (int i = 1; i <= n; i++) { cin >> b[i]; } sort(b + 1, b + n + 1); long long ans = 1; for (int i = n, j = n; j; j--) { while (a[i] > b[j] && i) { i--; } ans = ans * (j - i) % M; } cout << ans << "\n"; } return 0; }