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:

• Each pair of paths intersects at most once
• Each path stays within the bounding box of all the points.
• No three paths intersect at a single point.

The Intersection Sequence of \(Path_i\) is the ordered sequence \([s_1, s_2, .., s_K]\) such that

• \(Path_i\) and \(Path_{s_j}\) intersects \(\forall \space j \in [1,K]\)
• Intersection point of \(Path_i\) and \(Path_{s_j}\) occurs before intersection point of \(Path_i\) and \(Path_{s_{j+1}}\) while moving from the top point to the bottom point of \(Path_i\) \(\forall \space j \in [1,K ).\)

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\).

Input Format:

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 Format:

Output T numbers, the answers to each problem.

Constraints

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\)