# Practice on Toph

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

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

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$`

`$[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$`

.

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$`

.

`$1 \leq T \leq 100$`

`$1 \leq A_i \leq n $`

for each element `$A_i$`

of `$A$`

.

`$1 \leq n \leq 100$`

Sum of `$n$`

over all testcases will be `$ \leq 1500 $`

.

`$1 \leq n \leq 500$`

Sum of `$n$`

over all testcases will be `$ \leq 4500 $`

.

`$1 \leq n \leq 5000$`

Sum of `$n$`

over all testcases will be `$ \leq 45000 $`

.

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.

Input | Output |
---|---|

2 3 1 1 1 4 3 1 2 4 | Case 1: 4 Case 2: 5 |

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]\}$`

.

Login to submit

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