Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Array Partition

By upobir · Limits 4s, 1.0 GB

Today Leena learnt about subarrays and partitions. Given an array $A$, a subarray of this array is a part of $A$ such that it’s elements are adjacent. For example, the array $[1, 2, 3]$ has subarrays $[1, 2]$, $[2, 3]$, $[1, 2, 3]$, $[2]$, etc. A parition of an array is dividing the array into some subarrays such that each index belongs to exactly one subarray. For example, $A$ can have these $3$ (and possibly many more) partitions: $\{ [1, 2], [3] \}, \{[1], [2], [3]\}, \{[1, 2, 3]\}$.

Now Leena has been thinking about how many partitions an array can have. But then she found out that not all partitions are important to her. Specifically she thinks partitions with these two properties are important:

  • You can make a sequence of $k$ numbers, with $i$-th number of the sequence belonging to the $i$-th subarray of the partition. Here, the length of sequence, $k$, should be equal to number of subarrays in the partition.
  • The sequence you make is non-decreasing, that is if the sequence is $x_1, x_2, \dots, x_k$ then $x_1 \leq x_2 \leq x_3 \leq \cdots \leq x_k$
Suppose you have the array $[3, 1, 2, 4]$ then, $\{[3], [1, 2, 4]\}, \{[3, 1], [2, 4]\}, \{[3, 1, 2, 4]\}$ etc. are important, but $\{[3], [1, 2], [4]\}, \{[3], [1], [2, 4]\}$ etc. are not.

Now given some array, Leena wants to count how many important partitions that array has. Since the answer can be large output the answer modulo $10^9+7$.

Input

The first line will contain the number of testcases, $T$, a positive integer.

Each testcase will start with a line containing a positive integer $n$, the number of elements of the array $A$. Next line will contain $n$ space separated integers $A_1, A_2, \dots, A_n$.

Constraints

$1 \leq T \leq 100$
$1 \leq A_i \leq n $ for each element $A_i$ of $A$.

Subtask 1 (15 points)

$1 \leq n \leq 100$
Sum of $n$ over all testcases will be $ \leq 1500 $.

Subtask 2 (15 points)

$1 \leq n \leq 500$
Sum of $n$ over all testcases will be $ \leq 4500 $.

Subtask 3 (70 points)

$1 \leq n \leq 5000$
Sum of $n$ over all testcases will be $ \leq 45000 $.

Output

For each testcase, output in a line, “Case $x$: $y$”, where $x$ is the case number and $y$ is the output for that testcase. See sample for details.

Sample

InputOutput
2
3
1 1 1
4
3 1 2 4
Case 1: 4
Case 2: 5

Explanation

Any partition of $[1, 1, 1]$ is interesting.

$[3, 1, 2, 4]$ has $5$ interesting partitions: $\{[3, 1, 2, 4]\}, \{[3, 1, 2], [4]\}, \{[3, 1], [2, 4]\}, \{[3, 1], [2], [4]\}, \{[3], [1, 2, 4]\}$.

Discussion

Statistics


25% Solution Ratio

NirjhorEarliest, 1M ago

serotoninFastest, 1.3s

serotoninLightest, 100 MB

serotoninShortest, 944B

Submit

Login to submit

Editorial

একটি গুরুত্বপূর্ন অ্যারের পার্টিশন এ আমরা একটি unique non-decreasing sequence বের করতে পারি। সেটা হল...