The Third Problem solution codeforces

The Third Problem solution codeforces-

You are given a permutation 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an of integers from 00 to 𝑛1n−1. Your task is to find how many permutations 𝑏1,𝑏2,,𝑏𝑛b1,b2,…,bn are similar to permutation 𝑎a.

Two permutations 𝑎a and 𝑏b of size 𝑛n are considered similar if for all intervals [𝑙,𝑟][l,r] (1𝑙𝑟𝑛1≤l≤r≤n), the following condition is satisfied:

MEX([𝑎𝑙,𝑎𝑙+1,,𝑎𝑟])=MEX([𝑏𝑙,𝑏𝑙+1,,𝑏𝑟]),MEX⁡([al,al+1,…,ar])=MEX⁡([bl,bl+1,…,br]),

where the MEXMEX of a collection of integers 𝑐1,𝑐2,,𝑐𝑘c1,c2,…,ck is defined as the smallest non-negative integer 𝑥x which does not occur in collection 𝑐c. For example, MEX([1,2,3,4,5])=0MEX⁡([1,2,3,4,5])=0, and MEX([0,1,2,4,5])=3MEX⁡([0,1,2,4,5])=3.

Since the total number of such permutations can be very large, you will have to print its remainder modulo 109+7109+7.

In this problem, a permutation of size 𝑛n is an array consisting of 𝑛n distinct integers from 00 to 𝑛1n−1 in arbitrary order. For example, [1,0,2,4,3][1,0,2,4,3] is a permutation, while [0,1,1][0,1,1] is not, since 11 appears twice in the array. [0,1,3][0,1,3] is also not a permutation, since 𝑛=3n=3 and there is a 33 in the array.

Input

Each test contains multiple test cases. The first line of input contains one integer 𝑡t (1𝑡1041≤t≤104) — 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 𝑛n (1𝑛1051≤n≤105) — the size of permutation 𝑎a.

The second line of each test case contains 𝑛n distinct integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (0𝑎𝑖<𝑛0≤ai) — the elements of permutation 𝑎a.

It is guaranteed that the sum of 𝑛n across all test cases does not exceed 105105.

Output

For each test case, print a single integer, the number of permutations similar to permutation 𝑎a, taken modulo 109+7109+7.

Example

input

Copy
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

output

Copy
2
1
1
4
72
Note

For the first test case, the only permutations similar to 𝑎=[4,0,3,2,1]a=[4,0,3,2,1] are [4,0,3,2,1][4,0,3,2,1] and [4,0,2,3,1][4,0,2,3,1].

For the second and third test cases, the given permutations are only similar to themselves.

For the fourth test case, there are 44 permutations similar to 𝑎=[1,2,4,0,5,3]a=[1,2,4,0,5,3]:

  • [1,2,4,0,5,3][1,2,4,0,5,3];
  • [1,2,5,0,4,3][1,2,5,0,4,3];
  • [1,4,2,0,5,3][1,4,2,0,5,3];
  • [1,5,2,0,4,3][1,5,2,0,4,3].

Solution – CLICK HERE

Leave a Comment