We define a function F, on a array , P ,as follows:

F(P) = ( length(P) ^distinct(P))%(10⁹+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⁹+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 A_i.

Ouput:

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

Constraints:

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

Scoring:

• subtask 1: 1 ≤ N ≤ 1000 ( 30 pts )
• subtask 2: 1 ≤ N ≤ 10⁵ ( 70 pts )