There are n points on X-axis, and their coordinates are (1, 0), (2, 0), . . . , (n, 0). The color of the point is (i,0) is ai. If two points have the same color, then a semi-circle centered at their midpoint on the X-axis, connecting them, is drawn with color ai in the first quadrant (this is thus the top half of the circle, with these two points on the diameter). Compute the number of intersections where 2 arcs of different colors intersect modulo 1000000007. Input A number of of inputs (≤ 150), each starting with n on a line, followed by a line with n numbers ai (1≤n≤100000,1≤ai ≤100000). Output For each input, output the answer on one line. Sample Input 1 1 8 12312321 Sample Output 0 8