All Possible Increasing Subsequences

3 seconds
64 MB
Medium
LOJ-1085 Udebug Debug
English

An increasing subsequence from a sequence {A1, A2 ... An} is defined by {Ai1, Ai2 ... Aik}, where the following properties hold:

  1. i1 < i2 < i3 < ... < ik, and
  2. Ai1 < Ai2 < Ai3 < ... < Aik.

Now you are given a sequence, you have to find the number of all possible increasing subsequences.

Input

Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case contains an integer n (1 ≤ n ≤ 105) denoting the number of elements in the initial sequence. The next line will contain n integers separated by spaces, denoting the elements of the sequence. Each of these integers will be fit into a 32 bit signed integer.

Output

For each case of input, print the case number and the number of possible increasing subsequences modulo 1000000007 (109 + 7).

Sample

Sample Input Sample Output

3 3 1 1 2 5 1 2 1000 1000 1001 3 1 10 11

Case 1: 5 Case 2: 23 Case 3: 7

Notes

  1. For the first case, the increasing subsequences are (1), (1, 2), (1), (1, 2), 2.
  2. Dataset is huge, use faster I/O methods.