提示: 欢迎访问OurACM平台。
Problem 1991 LIS

Accept: 34    Submit: 176
Time Limit: 3000 mSec    Memory Limit : 32768 KB

Problem Description

LIS is the longest increasing sequence in an array. For example, in the array {1, 2, 2, 3}, there length of the LIS is exactly 3. In the array, we could find that {1, 2, 3} occurs two times, so we say there are two “LIS” in the array above.

Now you are given an array which has no more than 10^5 elements, you are expected to calculate the number of “LIS” in the array. The answer may be so large, so just output the remainder of the answer after divided by 1000000007.

Input

The first line is one integer T indicates the number of the test cases. (T <= 30)

Then for every case, the first line is one integer N indicates the number of the number.

Then one line contains N integer indicate the number. (All the number is smaller than 10^9 and non-negative).

Output

Output one line.

First output “Case idx: ”, here idx is the case number count from 1.

Then output the remainder of the number of “LIS” in the sequence after divided by 1000000007.

Sample Input

3 3 1 2 2 4 5 3 1 1 10 1 2 2 2 3 3 3 3 3 4

Sample Output

Case 1: 2 Case 2: 4 Case 3: 15

Source

FOJ有奖月赛-2010年12月

Submit  Back  Status  Discuss