Count Permutations

★★★★★

3.3

18 votes

, Algorithms, Combinatorics, Linear Search, Observation

Details

Submissions

Discussion

Editorial

Problem

From a permutation $P$ of length $N$ , Alice constructs an array $A$ of length $N$ such that $A_i = \max(P_1, P_2,\dots, P_i)$ . For example, if $P = [2, 1, 3, 5,4 ]$ , then Alice constructs the array $A = [2, 2, 3, 5,5 ]$ .

You are given an array $A$ containing $N$ integers. Find the number of permutations of length $N$ from which Alice can construct the given array $A$ . Since the answer can be very large, print it modulo $(10^9+7)$ .

Input format

The first line contains $T$ denoting the number of test cases. The description of $T$ test cases is as follows:
For each test case:
- The first line contains a single integer $N$ denoting the size of array $A$ .
- The second line contains $N$ integers $A_1, A_2, \dots, A_N$ denoting the elements of $A$ .

Output format
For each test case, print the number of permutations, modulo $(10^9+7)$ of length $N$ from which the given array $A$ can be constructed.

Constraints

$1 \leq T \leq 10^4 \\ 1 \leq N \leq 10^5\\ \\1\leq A_i \le N \\ Sum\; of \; N\;over\;all\;test\;cases\;does\;not\;exceed\;3\cdot 10^5.$

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

Test case 1: The only permutation of length $3$ from which Alice can construct $A = [1,3,3]$ is $P = [1, 3,2].$

Test case 2: There is no permutation of length of $4$ from which Alice can construct $A =[2,2,2,2].$

Test case 3: The permutations of length $6$ from which Alice can construct $A = [2, 3, 5, 5, 5, 6]$ are $P = [2, 3, 4, 5, 4, 1, 6], P = [2, 3, 4, 5, 1, 4, 6]$ .