# Counting Orders solution codeforces

## Counting Orders solution codeforces

You are given two arrays 𝑎 and 𝑏 each consisting of 𝑛 integers. All elements of 𝑎 are pairwise distinct.

Find the number of ways to reorder 𝑎 such that 𝑎𝑖>𝑏𝑖��>�� for all 1𝑖𝑛1≤�≤�, modulo 109+7109+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 𝑡 (1𝑡1041≤�≤104). The description of the test cases follows.

The first line of each test case contains a single integer 𝑛 (2𝑛21052≤�≤2⋅105) — the length of the array 𝑎 and 𝑏.

The second line of each test case contains 𝑛 distinct integers 𝑎1�1𝑎2�2𝑎𝑛�� (1𝑎𝑖1091≤��≤109) — the array 𝑎. It is guaranteed that all elements of 𝑎 are pairwise distinct.

The second line of each test case contains 𝑛 integers 𝑏1�1𝑏2�2𝑏𝑛�� (1𝑏𝑖1091≤��≤109) — the array 𝑏.

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

## Counting Orders solution codeforces

For each test case, output the number of ways to reorder array 𝑎 such that 𝑎𝑖>𝑏𝑖��>�� for all 1𝑖𝑛1≤�≤�, modulo 109+7109+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