In a sequence of N integers A_{1..N}, a triple ⟨a, b, c⟩ is considered beautiful if A_{a} = A_{c} and 1 ≤ a < b < c ≤ N.
For example, a sequence A_{1..6} = {3, 1, 3, 7, 3, 7} has 6 beautiful triples:
Given a sequence of integers, determine how many beautiful triples are there in the sequence. Modulo the output with 1,000,000,007.
The first line of input contains an integer T (T ≤ 50) denoting the number of cases. Each case begins with an integer N (1 ≤ N ≤ 100,000) denoting the size of the integer sequence. The next line contains N integers A_{i} (1 ≤ A_{i} ≤ 100,000) representing the elements in A, for i = 1..N respectively.
For each case, output in a line "Case #X: Y" where X is the case number, starts from 1, and Y is the output for that particular case.
