## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [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 ${a}_{1},{a}_{2},\dots ,{a}_{n}$ of integers from $0$ to $n-1$. Your task is to find how many permutations ${b}_{1},{b}_{2},\dots ,{b}_{n}$ are similar to permutation $a$.

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

Solution Click Below:-  👉
👇👇👇👇👇

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

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

Input

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

The second line of each test case contains $n$ distinct integers ${a}_{1},{a}_{2},\dots ,{a}_{n}$ ($0\le {a}_{i}) — the elements of permutation $a$.

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

Output

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