1827A.md (1582B)
1 Source: https://codeforces.com/problemset/problem/1827/A 2 3 A. Counting Orders 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given two arrays $a$ and $b$ each consisting of $n$ integers. All elements of $a$ are pairwise distinct. 22 23 Find the number of ways to reorder $a$ such that $a_i \gt b_i$ for all $1 \le i \le n$, modulo $10^9 + 7$. 24 25 Two ways of reordering are considered different if the resulting arrays are different. 26 27 Input 28 29 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. 30 31 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$. 32 33 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. 34 35 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$. 36 37 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^{5}$. 38 39 Output 40 41 For each test case, output the number of ways to reorder array $a$ such that $a_i \gt b_i$ for all $1 \le i \le n$, modulo $10^9 + 7$. 42 43 Example 44 45 Input 46 47 ``` 48 5 49 50 6 51 52 9 6 8 4 5 2 53 54 4 1 5 6 3 1 55 56 3 57 58 4 3 2 59 60 3 4 9 61 62 1 63 64 2 65 66 1 67 68 3 69 70 2 3 4 71 72 1 3 3 73 74 12 75 76 2 3 7 10 23 28 29 50 69 135 420 1000 77 78 1 1 2 3 5 8 13 21 34 55 89 144 79 ``` 80 81 Output 82 83 ``` 84 32 85 0 86 1 87 0 88 13824 89 ```