The Third Problem solution codeforces-
You are given a permutation similar to permutation .of integers from to . Your task is to find how many permutations are
Two permutations similar if for all intervals ( ), the following condition is satisfied:and of size are considered
where theof a collection of integers is defined as the smallest non-negative integer which does not occur in collection . For example, , and .
Since the total number of such permutations can be very large, you will have to print its remainder modulo.
In this problem, a permutation of sizeis an array consisting of distinct integers from to in arbitrary order. For example, is a permutation, while is not, since appears twice in the array. is also not a permutation, since and there is a in the array.
Each test contains multiple test cases. The first line of input contains one integer( ) — the number of test cases. The following lines contain the descriptions of the test cases.
The first line of each test case contains a single integer( ) — the size of permutation .
The second line of each test case containsdistinct integers (
It is guaranteed that the sum ofacross all test cases does not exceed .
For each test case, print a single integer, the number of permutations similar to permutation , taken modulo .
5 5 4 0 3 2 1 1 0 4 0 1 2 3 6 1 2 4 0 5 3 8 1 3 7 2 5 0 6 4
2 1 1 4 72
For the first test case, the only permutations similar toare and .
For the second and third test cases, the given permutations are only similar to themselves.
For the fourth test case, there arepermutations similar to :