﻿ Fuzhou University OnlineJudge ﻿
Problem 1991 LIS

## 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
﻿