[Solution] The Third Problem Codeforces Solution

C. The Third Problem

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a permutation a1,a2,…,an$a_1,a_2,\dots ,a_n$ of integers from 0$0$ to n−1$n-1$. Your task is to find how many permutations b1,b2,…,bn$b_1,b_2,\dots ,b_n$ are similar to permutation a$a$.

Two permutations a$a$ and b$b$ of size n$n$ are considered similar if for all intervals [l,r]$[l,r]$ (1≤l≤r≤n$1\le l\le r\le n$), the following condition is satisfied:where the MEX$\mathrm{MEX}$ of a collection of integers c1,c2,…,ck$c_1,c_2,\dots ,c_k$ is defined as the smallest non-negative integer x$x$ which does not occur in collection c$c$. For example, MEX([1,2,3,4,5])=0$\mathrm{MEX}([1,2,3,4,5])=0$, and MEX([0,1,2,4,5])=3$\mathrm{MEX}([0,1,2,4,5])=3$

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

Since the total number of such permutations can be very large, you will have to print its remainder modulo 109+7${10}^9+7$.

In this problem, a permutation of size n$n$ is an array consisting of n$n$ distinct integers from 0$0$ to n−1$n-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 1$1$ appears twice in the array. [0,1,3]$[0,1,3]$ is also not a permutation, since n=3$n=3$ and there is a 3$3$ in the array.

Input

The Third Three Number Problem Codeforces Solution

Almost Ternary Matrix Codeforces Solution

The Third Problem Codeforces Solution

Almost Triple Deletions CodeForces Solution

Three Days Grace Codeforces Solution

Each test contains multiple test cases. The first line of input contains one integer t$t$ (1≤t≤104$1\le t\le {10}^4$) — 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$n$ (1≤n≤105$1\le n\le {10}^5$) — the size of permutation a$a$.

The second line of each test case contains n$n$ distinct integers a1,a2,…,an$a_1,a_2,\dots ,a_n$ (0≤ai<n$0\le a_i<n$) — the elements of permutation a$a$.

It is guaranteed that the sum of n$n$ across all test cases does not exceed 105${10}^5$.

Output

For each test case, print a single integer, the number of permutations similar to permutation a$a$, taken modulo 109+7${10}^9+7$.