An increasing subsequence from a sequence {A₁, A₂ ... A_n} is defined by {A_i1, A_i2 ... A_ik}, where the following properties hold:

1. i₁ < i₂ < i₃ < ... < i_k, and
2. A_i1 < A_i2 < A_i3 < ... < A_ik.

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

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

Each case contains an integer n (1 ≤ n ≤ 10⁵) 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.

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

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.