Array Partition

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:

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

Input	Output
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]\}$.