sub-aaray-waala

We define a function F, on a array , P ,as follows:
F(P) = ( length(P)^

distinct(P))%(10^9+7)
where:
 length(P) denotes the number of elements in array P.
 distinct(P) denotes number of distinct elements in array P.

Ma5termind loves creating new challenges and he need your help testing his newest one. Given a array A consisting of N elements, compute the maximum value of F over all possible subarrays of A.

As result can be quite large, print it modulo 10^9+7.

Input:
Each input file will contain a T test cases.

First line will contain a single integer N denoting number of elements in array A.

Next line will contain a list of N integers Ai.

Ouput:
For each test case, output the answer in new line.

Constraints:

1 ≤ T ≤ 5 
1 ≤ N ≤ 100000
1 ≤ A[i] ≤ 100000000

See sample I/O for more clarification.

Scoring:

subtask 1: 1 ≤ N  ≤ 1000 ( 30 pts )
subtask 2: 1 ≤ N  ≤ 10^5 ( 70 pts )

SAMPLE INPUT
1
2
1 2

SAMPLE OUTPUT
4

Explanation

The maximum value of is for sub-array {1,2}.

Source: hackerearth | Difficulty: EASY


Solutions: