Yet Another Counting Problem ( DSA INTERVIEW PREPARATION PROBLEMS AND SOLUTIONS )

 Nayra doesn't like stories of people receiving random arrays as birthday presents, but this time she received an array as a present for her own birthday! After struggling for a day trying to figure out what to do with this array, she asked Aryan for help. He gave her this problem.

You are given an array A=[A1,A2,…,AN]$A=[A_1,A_2,\dots ,A_N]$ containing N$N$ distinct integers. Count the number of ways to form (unordered) sets of disjoint increasing subsequences of A$A$.

Formally, count the number of sets S={S1,S2,…,Sk}$S=\{S_1,S_2,\dots ,S_k\}$ such that:

• Each Si$S_i$ is an increasing subsequence of A$A$.
• If i≠j$i\ne j$, Si$S_i$ and Sj$S_j$ are disjoint, i.e, i≠j⟹Si∩Sj=∅$i\ne j⟹S_i\cap S_j=\mathrm{\varnothing }$

Note that it is not necessary that the sequences S1,S2,…,Sk$S_1,S_2,\dots ,S_k$ form a partition of A$A$ - in other words, some elements of A$A$ may not be in any chosen subsequence.

Two sets are considered equal if they contain the same subsequences. For example, the sets {[1,2],[3]}$\{[1,2],[3]\}$ and {[3],[1,2]}$\{[3],[1,2]\}$ are considered to be the same and should only be counted once.

Note that the final answer can be rather large, so compute its remainder after dividing it by 109+7${10}^9+7$.

Please refer to the sample for a few examples.

Input Format

• The first line of input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
• The first line of each test case contains a single integer N$N$ - the size of A$A$.
• The second line contains N$N$ distinct space-separated integers A1,A2,…,AN$A_1,A_2,\dots ,A_N$ - the elements of A$A$.

Output Format

For each test, print one line containing a single integer, the answer to the problem modulo (109+7)$({10}^9+7)$.

Constraints

• 1≤T≤2000$1\le T\le 2000$
• 1≤N≤20$1\le N\le 20$
• 1≤Ai≤N$1\le A_i\le N$
• The elements of A$A$ are distinct.
• Each input file contains at most 3$3$ tests with N>10$N>10$.

Subtasks

Subtask 1 (15 points):

• N≤14$N\le 14$

Subtask 2 (15 points):

• N≤16$N\le 16$

Subtask 3 (40 points):

• N≤18$N\le 18$

Subtask 4 (30 points):

• N≤20$N\le 20$

Sample Input 1 

2
2
1 2
7
1 2 7 3 6 4 5

Sample Output 1 

5
1537

Explanation

Test case 1: All possible sets are {},{[1]},{[2]},{[1],[2]},{[1,2]}$\{\},\{[1]\},\{[2]\},\{[1],[2]\},\{[1,2]\}$. Note that the empty set is also counted; and it is not necessary to use every element of A$A$ in some increasing subsequence.

Test case 2: Some of the valid possible ways are:

• S={[1,2,7],[3,6],[4]}$S=\{[1,2,7],[3,6],[4]\}$.
• S={[1,2,6],[7],[3],[4]}$S=\{[1,2,6],[7],[3],[4]\}$
• S={[1,2,6],[7],[3,5],[4]}$S=\{[1,2,6],[7],[3,5],[4]\}$
• S={[1,2,6],[7],[3,4]}$S=\{[1,2,6],[7],[3,4]\}$
• S={[1,4],[2,3],[6],[7]}$S=\{[1,4],[2,3],[6],[7]\}$

Once again, note that we count unordered sets. So, the following sets are considered the same:

• {[1,4],[2,3],[6],[7]}$\{[1,4],[2,3],[6],[7]\}$ or
• {[6],[1,4],[2,3],[7]}$\{[6],[1,4],[2,3],[7]\}$ or
• {[1,4],[6],[2,3],[7]}$\{[1,4],[6],[2,3],[7]\}$ or

• Tweet
• Share
• Share
• Share
• Share

Related Post