All Tracks Math Combinatorics Inclusion-Exclusion Problem

Permutation Intersections
Tag(s):

Dynamic Programming, Inclusion Exclusion, Medium-Hard, approved

Problem
Editorial
Analytics

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]$$
way 1 way 2

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 cases$$T$$.
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$$

SAMPLE INPUT
5
3
1 2 3
3
3 2 1
2
1 2
1
1
5
5 3 2 1 4
SAMPLE OUTPUT
1
2
1
1
8
Explanation

The second sample is illustrated in the statement.

Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

December Clash '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications