SOLVE
LATER
You are given two horizontal rows of points. Each row has N points. You are also given a permutation P of \([1,2,..N]\).
The \(i^{th}\) point in the top row has label i and has coordinates \((i, 1)\).
The \(i^{th}\) point in the bottom row has label \(P_i\) and has coordinates \((i, 0)\).
You will now draw N paths connecting the
\(i^{th}\) point in the top row to the \(j^{th}\) point in the bottom row where \(P_j = i\). Denote this path as \(Path_i\). The paths do not necessarily have to be straight lines.
The paths need to satisfy the following conditions:
The Intersection Sequence of \(Path_i\) is the ordered sequence \([s_1, s_2, .., s_K]\) such that
Following figure shows the intersection sequences for \(P =[3,2,1]\)
After drawing all the paths, you record the intersection sequence for each individual path. You are now wondering, what is the number of lists of intersection sequences you can write down. Two lists are considered different if there exists a path which has different intersection sequences in the two lists. As this number can get large, output it modulo \(10^9+7\).
The first line will contain the number of test casesT.
Each test case can be described with two lines.
The first line will contain a single integer N.
The second line will contain N space separated integers \(P_1,P_2,...,P_N\).
Output T numbers, the answers to each problem.
For all subtasks:
\(1 ≤ T ≤ 10^5\)
\(1 ≤ N\)
\(P_1,P_2,...,P_N\) will be a permutation of \(1,2,...,N\).
File 1 (50 pts)
\(N ≤ 4\)
File 3 (50 pts)
\(N ≤ 9\)
The second sample is illustrated in the statement.